3183. 湮灭

【题目描述】

在一个$ n $个点的树上, 每条边的边权为$ 1$, 有$ m $个元素会出现. 第$ i $个元素出现的时间为$ t_i$, 以 $c_i$个单位每秒的速度从$ a_i $移动到 $b_i$,如果某个时刻任意两个元素相撞了(可能在边上相撞) 就会引起爆炸, 然后整个宇宙会毁灭, 现在全能的神将问题交给了你, 他希望你能告诉他宇宙毁灭的确切时间, 即最早的两个元素相撞的时刻.

【输入格式】

第一行两个正整数 $n$,$ m$.

接下来$ n-1$ 行, 每行两个整数, 表示一条树上的边.

接下来$ m$ 行, 每行四个整数 $t_i$, $c_i$, $a_i$, $b_i$, 描述一个元素.

【输出格式】

输出一行一个小数, 表示最早的相撞时间, 精确到小数点后 $6 $位小数.

【样例输入】

6 4
2 5
6 5
3 6
4 6
4 1
27 6 1 3
9 5 1 6
27 4 3 4
11 29 2 6

【样例输出】

27.3

【提示】

对于所有的数据, $n$,$ m $≤ $10^5$,$ t_i$,$ c_i $≤$ 10^4$.