AT_arc165_c [ARC165C] Social Distance on Graph

[problemUrl]: https://atcoder.jp/contests/arc165/tasks/arc165_c 頂点に $ 1 $ から $ N $ の番号が付いた $ N $ 頂点からなる単純連結無向グラフがあります。グラフには重みを持つ辺が $ M $ 本あり、$ i $ 番目の辺は頂点 $ A_i,B_i $ を結ぶ重みが $ W_i $ の辺です。また、$ 2 $ 頂点を結ぶ単純パスの重みを、単純パスが含む辺の重みの総和とします。 各頂点に対し赤、青のいずれかの色を塗ります。以下の条件を満たす塗り分け方が存在するような整数 $ X $ の最大値を求めてください。 - 同じ色で塗られた相異なる $ 2 $ 頂点を結ぶどの単純パスについても、単純パスの重みは $ X $ 以上である。 単純パスとは グラフ $ G $ 上の頂点 $ X,Y $ に対して、頂点列 $ v_1,v_2,\ \ldots,\ v_k $ であって、 $ v_1=X $, $ v_k=Y $ かつ、$ 1\leq\ i\leq\ k-1 $ に対して $ v_i $ と $ v_{i+1} $ が辺で結ばれているようなものを頂点 $ X $ から頂点 $ Y $ への **ウォーク** と呼びます。 さらに、$ v_1,v_2,\ \ldots,\ v_k $ がすべて異なるようなものを頂点 $ X $ から頂点 $ Y $ への **単純パス** (あるいは単に **パス**) と呼びます。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ M $ $ A_1 $ $ B_1 $ $ W_1 $ $ A_2 $ $ B_2 $ $ W_2 $ $ \vdots $ $ A_M $ $ B_M $ $ W_M $

答えを出力してください。

### 制約 - $ 3\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ N-1\ \leq\ M\ \leq\ \min(\frac{N(N-1)}{2},2\ \times\ 10^5) $ - $ 1\ \leq\ A_i\