AT_abc214_d [ABC214D] Sum of Maximum Weights

[problemUrl]: https://atcoder.jp/contests/abc214/tasks/abc214_d $ N $ 頂点の木があり、頂点は $ 1,\ 2,\ \dots,\ N $ と番号付けられています。 $ i\ \,\ (1\ \leq\ i\ \leq\ N\ -\ 1) $ 番目の辺は頂点 $ u_i $ と頂点 $ v_i $ を結び、重みは $ w_i $ です。 異なる頂点 $ u,\ v $ に対し、頂点 $ u $ から頂点 $ v $ までの最短パスに含まれる辺の重みの最大値を $ f(u,\ v) $ とおきます。 $ \displaystyle\ \sum_{i\ =\ 1}^{N\ -\ 1}\ \sum_{j\ =\ i\ +\ 1}^N\ f(i,\ j) $ を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ u_1 $ $ v_1 $ $ w_1 $ $ \vdots $ $ u_{N\ -\ 1} $ $ v_{N\ -\ 1} $ $ w_{N\ -\ 1} $

答えを出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 10^5 $ - $ 1\ \leq\ u_i,\ v_i\ \leq\ N $ - $ 1\ \leq\ w_i\ \leq\ 10^7 $ - 与えられるグラフは木である。 - 入力は全て整数である。 ### Sample Explanation 1 $ f(1,\ 2)\ =\ 10,\ f(2,\ 3)\ =\ 20,\ f(1,\ 3)\ =\ 20 $ であるので、これらの和である $ 50 $ を出力します。