#codefestival2018finalh. [code_festival_2018_final_h]Pothunter
[code_festival_2018_final_h]Pothunter
问题文
AtCoder共和国由编号从到的城镇和编号从到的条道路组成。每个城镇都可以通过道路到达。
道路是一条双向连接城镇和的道路,需要花费时间进行移动。
AtCoder共和国将举办编号为到的个现场比赛。
比赛将在城镇举行,开始时间为,结束时间为。此外,比赛的冠军奖金为日元。
赏金猎人高桥想要尽可能多地获得奖金。因为高桥很强,他能在参加的每个比赛中获胜。
为了参加比赛,高桥需要在满足的所有时刻都在城镇,且不参加其他比赛。请参阅示例以获取详细信息。
请计算在时刻,高桥可以位于任意位置的情况下,他可以获得的总奖金的最大值。
制约条件
- 输入都是整数
- 所有城镇都可以通过道路到达
输入
从标准输入读取输入数据,输入格式如下:
:
:
输出
输出答案。
输入例子 1
5 4
1 2 2
2 3 3
2 4 1
4 5 5
1 5 1 5
2 5 3 7
8 15 4 5
12 16 5 9
输出例子 1
10
- 在时刻,位于城镇
- 停留直到时刻
- 在时刻参加在城镇举办的比赛
- 在时刻移动到城镇
- 在时刻移动到城镇
- 在时刻参加在城镇举办的比赛
- 获得的总奖金为,这是最大值
输入例子 2
11 10
5 9 1
2 9 5
4 8 4
2 6 1
3 7 3
5 8 2
2 11 5
3 11 1
1 4 3
9 10 3
1 7 11 10
2 8 9 12
8 15 3 11
2 3 2 4
3 6 4 6
7 9 5 9
4 8 1 7
11 18 6 9
10 14 6 4
5 11 7 11
输出例子 2
21
输入例子 3
2 6
1 2 1000000000
1 2 1 1000000000
3 4 1 1000000000
5 6 1 1000000000
7 8 1 1000000000
899999999 900000000 1 1000000000
999999999 1000000000 2 1000000000
输出例子 3
5000000000
- 注意答案可能非常大