题目描述

小 w 和小 c 在 H 国，近年来，随着 H 国的发展，H 国的道路也在不断变化着。

根据 H 国的道路法，H 国道路都有一个值 $w$，表示如果小 w 和小 c 通过这条道路，那么他们的 $L$ 值会减少 $w$，但是如果小 w 和小 c 在之前已经经过了这条路，那么他们的 $L$ 值不会减少。

H 国有 $N$ 个国家，最开始 H 国有 $N-1$ 条道路，这 $N-1$ 条道路刚好构成一棵树。

小 w 将和小 c 从 H 国的城市 $1$ 出发，游览 H 国的所有城市，总共游览 $32766$ 天，对于每一天，他们都希望游览结束后 $L$ 值还是一个正数，求他们出发时 $L$ 值至少为多少。

H 国的所有边都是无向边，没有一条道路连接相同的一个城市。

输入格式

输入第 1 行，一个整数 $N$。

输入第 2 至第 $N$ 行，每行三个正整数 $u, v, w$，表示城市 $u$ 与城市 $v$ 有一条值为 $w$ 道路。

输入第 $N+1$ 行，一个整数 $M$，表示 H 国有 $M$ 条正在变化的道路。

输入第 $N+2$ 行到第 $N+M+1$ 行，每行 5 个整数 $u, v, w, l, r$，表示城市 $u$ 到城市 $v$ 有一条值为 $w$ 的道路，这条道路存在于第 $l$ 天到第 $r$ 天。

输出格式

输出共 $32766$ 行，第 $i$ 行表示第 $i$ 天游览的 $L$ 值至少为多少。

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

提示

第一天，选择 $1 \xrightarrow{1} 2 \xrightarrow{0} 1 \xrightarrow{3} 3 \xrightarrow{2} 4$，$L$ 值总共减少了 $6$，所以 $L$ 值至少为 $7$。

第二天，选择 $1 \xrightarrow{1} 2 \xrightarrow{0} 1 \xrightarrow{3} 3 \xrightarrow{4} 4$，$L$ 值总共减少了 $8$，所以 $L$ 值至少为 $9$。

第三天及之后，选择 $1 \xrightarrow{3} 3 \xrightarrow{4} 4 \xrightarrow{5} 2$，$L$ 值总共减少了 $12$，所以 $L$ 值至少为 $13$。

subtask1 : 15分，$N = 100, rm = 233$。

subtask2 : 15分，$N = 1000, rm = 2333$。

subtask3 : 20分，$N = 49998, rm = 32766, l = r$。

subtask4：20分，$N = 49999, rm = 32766, r = rm$。

subtask5：30分，$N = 50000, rm = 32766$。

对于 subtask3，$M = rm$；对于其他 subtask，$M=3\times rm$。

对于所有数据 : $1\leq N\leq 50000, 1\leq l\leq r\leq rm\leq 32766, 1\leq w\leq 10^9$。