#codefestival2018finalh. [code_festival_2018_final_h]Pothunter

[code_festival_2018_final_h]Pothunter

問題文

AtCoder共和国は 11 から NN までの番号がついた町と 11 から N1N-1 の番号がついた N1N-1 本の道からできています。それぞれの町は道をたどって到達可能です。

ii は町 AiA_iBiB_i を双方向につなぐ道で、移動に DiD_i だけ時間がかかります。

AtCoder共和国で 11 から MM までの番号がついた MM 個のオンサイトコンテストが開催されることになりました。

コンテスト ii は町 CiC_i で開催され、開始時刻は SiS_i で終了時刻は EiE_i です。また、コンテストの優勝賞金は XiX_i 円です。

賞金稼ぎの高橋君は、賞金をできる限りたくさんもらいたいです。高橋君はとても強いので参加したコンテスト全てで優勝可能です。

高橋君がコンテスト ii に参加するためには、Sileqt<EiS_i \\leq t < E_i を満たすいずれの時刻 tt においても町 CiC_i にいて他のコンテストに参加していない必要があります。 詳しくはサンプル 11 も参照してください。

高橋君が時刻 00 の時点で好きな位置にいることができるときの、高橋君が得られる賞金の総和の最大値を求めてください。

制約

  • 1leqN,Mleq7times1041 \\leq N,M \\leq 7 \\times 10^{4}
  • 1leqAi<BileqN1 \\leq A_i < B_i \\leq N
  • 1leqDi,Xileq1091 \\leq D_i,X_i \\leq 10^{9}
  • 1leqSi<Eileq1091 \\leq S_i < E_i \\leq 10^{9}
  • 1leqCileqN1 \\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
  • 答えは非常に大きくなりうることに注意してください