#codefestival2018finalh. [code_festival_2018_final_h]Pothunter

[code_festival_2018_final_h]Pothunter

问题文

AtCoder共和国由编号从11NN的城镇和编号从11N1N-1N1N-1条道路组成。每个城镇都可以通过道路到达。

道路ii是一条双向连接城镇AiA_iBiB_i的道路,需要花费时间DiD_i进行移动。

AtCoder共和国将举办编号为11MMMM个现场比赛。

比赛ii将在城镇CiC_i举行,开始时间为SiS_i,结束时间为EiE_i。此外,比赛的冠军奖金为XiX_i日元。

赏金猎人高桥想要尽可能多地获得奖金。因为高桥很强,他能在参加的每个比赛中获胜。

为了参加比赛ii,高桥需要在满足Sit<EiS_i\leq t < E_i的所有时刻tt都在城镇CiC_i,且不参加其他比赛。请参阅示例11以获取详细信息。

请计算在时刻00,高桥可以位于任意位置的情况下,他可以获得的总奖金的最大值。

制约条件

  • 1N,M7×1041 \leq N, M \leq 7 \times 10^{4}
  • 1Ai<BiN1 \leq A_i < B_i \leq N
  • 1Di,Xi1091 \leq D_i,X_i \leq 10^{9}
  • 1Si<Ei1091 \leq S_i < E_i \leq 10^{9}
  • 1CiN1 \leq C_i \leq N
  • 输入都是整数
  • 所有城镇都可以通过道路到达

输入

从标准输入读取输入数据,输入格式如下:

NN MM

A1A_1 B1B_1 D1D_1

:

AN1A_{N-1} BN1B_{N-1} DN1D_{N-1}

S1S_1 E1E_1 C1C_1 X1X_1

:

SMS_{M} EME_{M} CMC_{M} XMX_{M}

输出

输出答案。


输入例子 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
  • 在时刻00,位于城镇11
  • 停留直到时刻11
  • 在时刻11参加在城镇11举办的比赛11
  • 在时刻55移动到城镇22
  • 在时刻77移动到城镇44
  • 在时刻88参加在城镇44举办的比赛33
  • 获得的总奖金为1010,这是最大值

输入例子 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
  • 注意答案可能非常大