题目描述

小 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 -(1)> 2 -(0)> 1 -(3)> 3 -(2)> 4，L 值总共减少了 6，所以 L 值至少为 7

第二天，选择 1 -(1)> 2 -(0)> 1 -(3)> 3 -(4)> 4，L 值总共减少了 8，所以 L 值至少为 9

第三天及之后，选择 1 -(3)> 3 -(4)> 4 -(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$