AT_ddcc_2016_qual_d 道路網
Description
[problemUrl]: https://atcoder.jp/contests/ddcc2016-qual/tasks/ddcc_2016_qual_d
$ N $ 個の都市と $ N-1 $ 個の道からなる国があります。各都市には $ 1,\ \,\ 2,\ \,\ …\ \,\ ,\ \,\ N $ と番号がついています。 $ i(1\ ≦\ i\ ≦\ N-1) $ 番目の道は都市 $ A_i $ と都市 $ B_i $ を長さ $ C_i $ でつないでいます。 道は双方向に移動可能で、どの都市同士も何本かの道を通って互いに行き来することが可能です。
ある日、$ 1≦i\
Input Format
入力は以下の形式で標準入力から与えられる。
> $ N $ $ X $ $ A_1 $ $ B_1 $ $ C_{1} $ $ . $ $ . $ $ . $ $ A_{N-1} $ $ B_{N-1} $ $ C_{N-1} $
Output Format
答えを $ 1 $ 行に出力せよ。
Explanation/Hint
### 制約
- $ 2\ ≦\ N\ ≦\ 10^{5} $
- $ 1\ ≦\ A_i,\ \,\ B_i\ ≦\ N(1\ ≦\ i\ ≦\ N-1) $
- $ 1\ ≦\ C_i\ ≦\ 10^{5}(1\ ≦\ i\ ≦\ N-1) $
- $ 1\ ≦\ X\ ≦\ 10^5 $
- 操作が行われる以前の時点において、どの $ 2 $ つの都市同士も何本かの道をたどって移動可能
- $ C_i,\ \,\ X $ はいずれも整数
### Sample Explanation 1
以下の図は都市と道の関係を表します。青い実線は元々あった $ N-1 $ 本の道を、黒い破線は操作により新たに追加された長さ $ 3 $ の道を表しています。
