0655 - 切符の手配 (Arranging Tickets)

JOI 国には N 個の駅 1, 2, ..., N がある．これらは，円形の線路に沿って時計回りに順に並んでいる．

鉄道に乗るための切符は N 種類あり，それぞれ 1, 2, ..., N の番号が付けられている．切符 i (1 ≤ i ≤ N - 1) を 1 枚用いると，駅 i から駅 i + 1，または駅 i + 1 から駅 i へ 1 人が移動できる．また，切符 N を 1 枚用いると，駅 1 から駅 N，または駅 N から駅 1 へ 1 人が移動できる．これらの切符は，N 種類の切符をちょうど 1 枚ずつ含む N 枚セットの形でのみ販売されている．

あなたは，JOI 国の旅行会社で切符の手配をする業務を行っている．本日，あなたは M 件の依頼を受けた．i 番目(1 ≤ i ≤ M) の依頼は，駅 A_i から駅 B_i に C_i 人が移動したい，というものである．ただし，移動する C_i 人は，全員が同じ経路で移動する必要はない．

これらの依頼をすべて処理するために，切符を最小で何セット購入する必要があるかを求めたい．

課題

駅の数および依頼の情報が与えられたとき，購入すべき切符のセット数の最小値を求めるプログラムを作成せよ．

入力

標準入力から以下のデータを読み込め．

• 1 行目には，2 個の整数 N, M が空白を区切りとして書かれている．これは，JOI 国に N 個の駅があり，あなたが M 件の依頼を受けたことを表す．
• 続く M 行のうちの i 行目（1 ≤ i ≤ M）には，3 個の整数 A_i, B_i, C_i が空白を区切りとして書かれている．これは，i 番目の依頼が駅 A_i から駅 B_i に C_i 人が移動したい，というものであることを表す．

出力

標準出力に購入すべき切符のセット数の最小値を 1 行で出力せよ．

制限

すべての入力データは以下の条件を満たす．

• 3 ≤ N ≤ 200 000．
• 1 ≤ M ≤ 100 000．
• 1 ≤ A_i ≤ N (1 ≤ i ≤ M)．
• 1 ≤ B_i ≤ N (1 ≤ i ≤ M)．
• 1 ≤ C_i ≤ 1 000 000 000 (1 ≤ i ≤ M)．
• A_i ≠ B_i (1 ≤ i ≤ M)．

小課題

この課題では小課題は全部で 5 個ある．各小課題の配点および追加の制限は以下の通りである．

小課題1 [10 点]

• N ≤ 20．
• M ≤ 20．
• C_i = 1 (1 ≤ i ≤ M)．

小課題2 [35 点]

• N ≤ 300．
• M ≤ 300．
• C_i = 1 (1 ≤ i ≤ M)．

小課題3 [20 点]

• N ≤ 3 000．
• M ≤ 3 000．
• C_i = 1 (1 ≤ i ≤ M)．

小課題4 [20 点]

• C_i = 1 (1 ≤ i ≤ M)．

小課題5 [15 点]

追加の制限はない．

入出力例

入力例 1

3 3
1 2 1
2 3 1
3 1 1

出力例 1

1

全員が時計回りに移動すると，それぞれの切符は 1 枚ずつ必要となるので，1 セット購入すればよい．

入力例 2

3 2
1 2 4
1 2 2

出力例 2

3

次のように移動することで，それぞれの切符は 3 枚ずつ必要となる．

• 最初の依頼において，3 人が時計回りに，1 人が反時計回りに移動する．
• 2 番目の依頼において，2 人が反時計回りに移動する．

したがって，3 セット購入すればよい．

2 セットで移動することはできないので，3 を出力する．

入力例 3

6 3
1 4 1
2 5 1
3 6 1

出力例 3

2

例えば，切符を 2 セット購入して，以下のように配ればよい．

• 駅 1 から駅 4 に移動したい人に，切符 1, 2, 3 を配る．
• 駅 2 から駅 5 に移動したい人に，切符 1, 6, 5 を配る．
• 駅 3 から駅 6 に移動したい人に，切符 3, 4, 5 を配る．

1 セットで移動することはできないので，2 を出力する．