G. Path to Pluto
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In celebration of the 300th anniversary of the naming of Pluto, the Plutonian government is hosting a massive event. Pluto was just one of many planets to eventually be discovered, and by now there are $$$n$$$ ($$$2 \leq n \leq 10^5$$$) planets in the solar system. Pluto is planet $$$1$$$. There are also currently $$$n - 1$$$ unidirectional roads between planets. Each road leads from one planet to another, and each road also has a fee for traveling across.

For each planet $$$i$$$ ($$$1 \leq i \leq n$$$), its travel cost $$$t_i$$$ is the minimum cost over all paths from planet $$$i$$$ to Pluto (planet $$$1$$$). The Plutonian government wants to minimize the sum of the travel cost over all planets, and to help, they can afford to construct at most one new road between any two planets with cost $$$C$$$. Please help the Plutonian government decide where to construct one road in order to minimize the sum of all travel costs.

Input

The first line of input contains integers $$$N$$$ and $$$C$$$. ($$$2 \leq N \leq 10^5$$$, $$$1 \leq C \leq 10^6$$$) These represent the number of planets and the travel fee on the additional road repectively.

The next $$$n - 1$$$ lines each contain integers $$$u_i$$$, $$$v_i$$$, and $$$c_i$$$ ($$$1 \leq u_i, v_i \leq N$$$, $$$1 \leq c_i \leq 10^6$$$), where $$$u_i$$$ and $$$v_i$$$ represent the start and end of the $$$i$$$th road respectively, and $$$c_i$$$ represents the fee for traveling across the road.

It is guaranteed that Pluto is reachable from all planets.

Output

The output should consist of a single integer representing the minimum sum of travel costs after adding at most one road. Note that the Plutonian government can decide not to add a road.

Examples
Input
4 2
2 1 4
3 1 8
4 1 6
Output
12
Input
5 2
2 1 3
3 1 10
4 3 5
5 3 6
Output
20
Input
8 255
2 1 320
5 1 345
7 5 590
4 2 110
3 2 290
6 5 235
8 1 915
Output
3455
Note

In the first test case, we can add the edge from planet $$$1$$$ to planet $$$3$$$, which makes the sum of all travel costs $$$0 + 4 + 2 + 6 = 12$$$. It can be proven that no other placement of the extra road can minimize this further.