变化的道路

题目描述

小 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 值至少为多少

输入输出样例

输入样例 #1

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

输出样例 #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$