Fuel and Pipes

個の節点と 本のパイプからなるネットワークがあります。 本目のパイプは 個目の節点と 個目の節点を相互に接続していて、どちらか片方の向きに、 秒間に最大で までの燃料を流すことができます。

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

• 入力はすべて整数である。

行に答えを出力せよ。

4
1 4 1
2 4 2
1 2 3
3 4 4
1 3 5

8

例えば、節点 に油田を建設し、節点 に工場を建設することで、秒間 を達成することができます。