問題文
N 個の節点と M 本のパイプからなるネットワークがあります。 i 本目のパイプは Ai 個目の節点と Bi 個目の節点を相互に接続していて、どちらか片方の向きに、 1 秒間に最大で Ci [L] までの燃料を流すことができます。
節点から二つ選び、片方に油田、もう片方に工場を建設します。このとき、 1 秒あたりに、油田から工場まで最大で何 [L] の燃料を流せるか答えてください。
制約
- 2≤N≤100
- 1≤M≤100
- 1≤Ai,Bi≤N
- 1≤Ci≤109
- 入力はすべて整数である。
入力
出力
1 行に答えを出力せよ。
入出力例
入力例1
4
1 4 1
2 4 2
1 2 3
3 4 4
1 3 5
例えば、節点 1 に油田を建設し、節点 3 に工場を建設することで、秒間 8 [L] を達成することができます。