Read problems statements in Mandarin chinese, Russian and Vietnamese as well.

Archi is a small boy from Uzhlyandia. For Chef's birthday, he prepared a tree with $N$ vertices (numbered $1$ through $N$). Each edge in this tree has a certain length.

There are $M$ speedsters on the tree, numbered $1$ through $M$. For each valid $i$, speedster number $i$ starts at time $t_{i}$ from vertex number $u_{i}$ and runs straight to vertex number $v_{i}$ with constant velocity $s_{i}$. Before time $t_{i}$, the speedster is not considered to be present in the tree.

Chef is interested in the following question: for each vertex, what is the smallest time when a speedster is present at this vertex?

------ Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
Each of the next $N-1$ lines contains three space-separated integers $u$, $v$ and $w$ denoting an edge between vertices $u$ and $v$ with length $w$.
The next line contains a single integer $M$.
For each valid $i$, the $i$-th of the next $M$ lines contains four space-separated integers $u_{i}$, $v_{i}$, $t_{i}$ and $s_{i}$ describing the $i$-th speedster.

------ Output ------
For each test case, print $N$ lines. For each valid $i$, the $i$-th of these lines should contain a single real number — the minimum time when the $i$-th vertex is visited by a speedster, or $-1$ if it is never visited. Your answer will be considered correct if its absolute or relative error does not exceed $10^{-6}$.

------ Constraints ------
$1 ≤ T ≤ 100$
$1 ≤ N, M ≤ 2 \cdot 10^{5}$
$1 ≤ u, v ≤ N$
$1 ≤ w, t, s ≤ 10^{9}$
the graph described on the input is a tree
the sum of $N$ for all test cases does not exceed $2 \cdot 10^{5}$
the sum of $M$ for all test cases does not exceed $2 \cdot 10^{5}$

------ Subtasks ------
Subtask #1 (10 points):
the sum of $N$ for all test cases does not exceed $5 \cdot 10^{3}$
the sum of $M$ for all test cases does not exceed $5 \cdot 10^{3}$

Subtask #2 (20 points): the velocities of all speedsters are identical

Subtask #3 (20 points): the tree is a bamboo (a path)

Subtask #4 (50 points): original constraints

------ Example Input ------

1
5
1 2 3
1 3 5
3 4 1
4 5 4
3
2 1 3 4
4 2 1 3
1 3 2 6

------ Example Output ------

2.0000000
3.0000000
1.3333333
1.0000000
-1

见题面

见题面