AT_ddcc2020_final_d Pars/ey

[problemUrl]: https://atcoder.jp/contests/ddcc2020-final/tasks/ddcc2020_final_d AtCoder 社の料理長を務めるあなたはよく高橋社長に自慢のハンバーグをふるまっていますが、せっかく仕入れたパセリを高橋社長が食べてくれず困っています。そこであなたは、パセリを一箇所でカットして食べやすくすることにしました。 パセリは $ N $ 頂点 $ N $ 辺の単純かつ連結な無向グラフで表され、頂点にも辺にも $ 1 $ から $ N $ までの番号がついています。辺 $ i $ は $ 2 $ 頂点 $ A_i,\ B_i $ をつないでおり、長さは $ C_i $ です。 連結な頂点対 $ (u,\ v) $ 全てに対して $ u,\ v $ 間の最短距離を求めたとき、その最大値をパセリの **硬さ** と定義します。 全ての $ i\ (1\ \leq\ i\ \leq\ N) $ に対して、辺 $ i $ のみを取り除いたパセリの硬さを求めてください。

N/A

N/A

### 制約 - 入力はすべて整数 - $ 3\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ A_i,\ B_i\ \leq\ N $ - $ 1\ \leq\ C_i\ \leq\ 10^9 $ - 与えられる無向グラフは単純かつ連結 ### Sample Explanation 1 \- 辺 $ 1 $ のみを取り除いたパセリにおいて、最短距離は $ (1,\ 5) $ 間の $ 9 $ が最大です。 - 辺 $ 2 $ のみを取り除いたパセリにおいて、最短距離は $ (2,\ 5) $ 間の $ 11 $ が最大です。 - 辺 $ 3 $ のみを取り除いたパセリにおいて、最短距離は $ (1,\ 5) $ 間の $ 10 $ が最大です。 - 辺 $ 4 $ のみを取り除いたパセリにおいて、最短距離は $ (4,\ 5) $ 間の $ 5 $ が最大です。 - 辺 $ 5 $ のみを取り除いたパセリにおいて、最短距離は $ (1,\ 4) $ 間の $ 4 $ が最大です。