#P18717. Discount Event
Discount Event
Discount Event
某国有 座城市和 条道路。城市编号为 到 ,道路编号为 到 。第 条道路双向连接城市 ,通行费用为 。任意两座城市之间都可以通过这些道路到达。
两座城市的距离定义为从一座城市前往另一座城市所需的最小费用。
作为道路公司的总裁,你准备在节日期间举办优惠活动,一共有 个方案。第 个方案把城市 与 之间最短路径上的所有道路费用改为 。请分别计算每个方案实施后,任意两座城市之间距离的最大值。
各方案独立,均基于原始道路费用计算;一个方案的修改不会保留到下一个方案。
输入格式
第一行一个整数 ,。
接下来 行,第 行三个整数 :
$$1\le a_i,b_i\le n,\quad a_i\ne b_i,\quad1\le w_i\le10^9.$$保证任意两座城市可以互相到达。因此给出的道路构成一棵树,两点之间的路径唯一。
下一行一个整数 ,。
接下来 行,每行两个整数 ,,且 。
输出格式
输出 行,第 行一个整数,表示第 个方案实施后的最大城市间距离。
完整原样例
5
1 2 1
1 3 2
2 4 4
2 5 2
3
1 4
3 5
5 4
4
4
3
5
1 2 2
1 3 3
1 4 5
1 5 4
3
1 2
1 4
4 5
9
7
5
8
1 2 3
1 3 5
2 4 5
2 5 3
2 6 6
6 7 1
6 8 2
7
1 2
1 3
2 4
2 5
2 6
6 7
6 8
13
13
16
16
13
16
15
7
1 2 3
1 3 4
2 4 2
2 5 1
3 6 6
3 7 2
6
1 2
1 3
1 4
1 5
1 6
1 7
12
11
11
12
7
11