問題文

NN 個の節点と MM 本のパイプからなるネットワークがあります。 ii 本目のパイプは AiA_i 個目の節点と BiB_i 個目の節点を相互に接続していて、どちらか片方の向きに、 11 秒間に最大で Ci [L]C_i\text{ [L]} までの燃料を流すことができます。

節点から二つ選び、片方に油田、もう片方に工場を建設します。このとき、 11 秒あたりに、油田から工場まで最大で何 [L]\text{[L]} の燃料を流せるか答えてください。

制約

  • 2N1002 \le N \le 100
  • 1M1001 \le M \le 100
  • 1Ai,BiN1 \le A_i, B_i \le N
  • 1Ci1091 \le C_i \le 10^9
  • 入力はすべて整数である。

入力

N MA1 B1 C1AM BM CMN\ M\\ A_1\ B_1\ C_1\\ \vdots\\ A_M\ B_M\ C_M

出力

11 行に答えを出力せよ。

入出力例

入力例1
4
1 4 1
2 4 2
1 2 3
3 4 4
1 3 5
出力例1
8

例えば、節点 11 に油田を建設し、節点 33 に工場を建設することで、秒間 8 [L]8\text{ [L]} を達成することができます。

提出


Go (1.21)