CF704E.Iron Man

Tony Stark is playing a game with his suits (they have auto-pilot now). He lives in Malibu. Malibu has n junctions numbered from 1 to n, connected with n - 1 roads. One can get from a junction to any other junction using these roads (graph of Malibu forms a tree).

Tony has m suits. There's a special plan for each suit. The i-th suit will appear at the moment of time t__i in the junction v__i, and will move to junction u__i using the shortest path between v__i and u__i with the speed c__i roads per second (passing a junctions takes no time), and vanishing immediately when arriving at u__i (if it reaches u__i in time q, it's available there at moment q, but not in further moments). Also, suits move continuously (for example if v__i ≠ u__i, at time it's in the middle of a road. Please note that if v__i = u__i it means the suit will be at junction number v__i only at moment t__i and then it vanishes.

An explosion happens if at any moment of time two suits share the same exact location (it may be in a junction or somewhere on a road; while appearing, vanishing or moving).

Your task is to tell Tony the moment of the the first explosion (if there will be any).

托尼·斯塔克正在和他的一套套战衣（如今已具备自动导航功能）玩一个游戏。他住在马里布。马里布共有 $ n $ 个路口，编号从 $ 1 $ 到 $ n $，由 $ n-1 $ 条道路连接。任意两个路口之间均可通过这些道路相互到达（即马里布的路网构成一棵树）。

托尼共有 $ m $ 套战衣。每套战衣都有一项特殊任务。第 $ i $ 套战衣将在时刻 $ t_i $ 出现在路口 $ v_i $，并以速度 $ c_i $（单位：条道路/秒）沿 $ v_i $ 与 $ u_i $ 之间的最短路径向路口 $ u_i $ 移动（经过路口不耗时），并在抵达 $ u_i $ 的瞬间立即消失（若它在时刻 $ q $ 抵达 $ u_i $，则它在时刻 $ q $ 仍位于 $ u_i $，但此后不再存在）。此外，战衣的移动是连续进行的（例如，若 $ v_i \ne u_i $，则在时刻 $ \displaystyle t_i + \frac{1}{2c_i} $，它恰好位于某条道路的中点）。请注意，若 $ v_i = u_i $，则表示该战衣仅在时刻 $ t_i $ 出现在路口 $ v_i $，随后立即消失。

当任意时刻有两个战衣处于完全相同的精确位置（该位置可以是一个路口，也可以是某条道路上的某个点；包括刚出现、正消失或正在移动的过程中），就会发生爆炸。

你的任务是告诉托尼：首次爆炸发生的时刻（如果会发生爆炸的话）。

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 100 000) — the number of junctions and the number of suits respectively.

The next n - 1 lines contain the roads descriptions. Each line contains two integers a__i and b__i — endpoints of the i-th road (1 ≤ a__i, b__i ≤ n, a__i ≠ b__i).

The next m lines contain the suit descriptions. The i-th of them contains four integers t__i, c__i, v__i and u__i (0 ≤ t__i ≤ 10 000, 1 ≤ c__i ≤ 10 000, 1 ≤ v__i, u__i ≤ n), meaning the i-th suit will appear at moment of time t__i at the junction v__i and will move to the junction u__i with a speed c__i roads per second.

输入的第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 100\,000$），分别表示路口的数量和套装（suit）的数量。

接下来的 $n-1$ 行描述道路。每行包含两个整数 $a_i$ 和 $b_i$，表示第 $i$ 条道路的两个端点（$1 \leq a_i, b_i \leq n$，且 $a_i \neq b_i$）。

接下来的 $m$ 行描述各套装。其中第 $i$ 行包含四个整数 $t_i$、$c_i$、$v_i$ 和 $u_i$（$0 \leq t_i \leq 10\,000$，$1 \leq c_i \leq 10\,000$，$1 \leq v_i, u_i \leq n$），表示第 $i$ 个套装将在时刻 $t_i$ 出现在路口 $v_i$，并以每秒 $c_i$ 条道路的速度向路口 $u_i$ 移动。

If there would be no explosions at all, print -1 in the first and only line of output.

Otherwise print the moment of the first explosion.

Your answer will be considered correct if its relative or absolute error doesn't exceed 10 - 6.

如果根本不会发生任何爆炸，则在输出的第一行且唯一一行中打印 $-1$。

否则，请输出第一次爆炸发生的时刻。

只要您的答案的相对误差或绝对误差不超过 $10^{-6}$，即视为正确。