問題文


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

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

制約


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

入力


出力


行に答えを出力せよ。

入出力例


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

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

Submit


Go (1.14)