Description

Xiao w and Xiao c are in Country H. In recent years, as Country H has developed, its roads have been constantly changing.

According to Country H’s road law, every road has a value $w$, meaning that if Xiao w and Xiao c pass through this road, their $L$ value will decrease by $w$. However, if Xiao w and Xiao c have already passed this road before, their $L$ value will not decrease.

Country H has $N$ cities. Initially, Country H has $N-1$ roads, and these $N-1$ roads form a tree.

Xiao w and Xiao c will start from city $1$ and visit all cities of Country H. They will travel for 32766 days in total. For each day, they want the $L$ value to still be positive after finishing the tour. Find the minimum initial $L$ they need at departure for each day.

All edges in Country H are undirected. No road connects a city to itself.

Input Format

Line 1: an integer $N$.

Lines 2 to $N$: each line contains three positive integers $u, v, w$, meaning there is a road of value $w$ between cities $u$ and $v$.

Line $N+1$: an integer $M$, meaning Country H has $M$ roads that are changing.

Lines $N+2$ to $N+M+1$: each line contains $5$ integers $u, v, w, l, r$, meaning there is a road of value $w$ from city $u$ to city $v$, and this road exists from day $l$ to day $r$.

Output Format

Output $32766$ lines. The $i$-th line is the minimum $L$ required on day $i$.

4
1 3 3
3 4 4
2 4 5
3
1 2 1 1 2
2 3 8 2 3
3 4 2 1 1

7
9
13
由于版面原因，仅显示三行，接下来32763行都是13

Hint

On day 1, choose $1 \xrightarrow{1} 2 \xrightarrow{0} 1 \xrightarrow{3} 3 \xrightarrow{2} 4$. The $L$ value decreases by $6$ in total, so the minimum $L$ is $7$.

On day 2, choose $1 \xrightarrow{1} 2 \xrightarrow{0} 1 \xrightarrow{3} 3 \xrightarrow{4} 4$. The $L$ value decreases by $8$ in total, so the minimum $L$ is $9$.

From day 3 onward, choose $1 \xrightarrow{3} 3 \xrightarrow{4} 4 \xrightarrow{5} 2$. The $L$ value decreases by $12$ in total, so the minimum $L$ is $13$.

Subtask 1: 15 points, $N = 100$, rm = 233.

Subtask 2: 15 points, $N = 1000$, rm = 2333.

Subtask 3: 20 points, $N = 49998$, rm = 32766, $l = r$.

Subtask 4: 20 points, $N = 49999$, rm = 32766, $r = rm$.

Subtask 5: 30 points, $N = 50000$, rm = 32766.

For subtask 3, $M = rm$; for other subtasks, $M = 3 \times rm$.

Constraints for all testdata: $1 \leq N \leq 50000$, $1 \leq l \leq r \leq rm \leq 32766$, $1 \leq w \leq 10^9$.

Translated by ChatGPT 5