410087: GYM103940 D District Capitalism Roads

You are the CEO of a big company that makes roads in the city, one day you are commissioned to make roads in the district capitalism, and of course, the names clearly tell you, that district capitalism is a district where they really love the capital city! You have seen the city and you love the city too so you decided to work for free, it's a normal thing in the capital city that everybody works for free.

There are $$$N$$$ cities numbered from $$$1$$$ to $$$N$$$, you have a list of $$$M$$$ roads that you can make, each road option is represented by three integers $$$A$$$, $$$B$$$, and $$$C$$$ which means that there is an option to connect city $$$A$$$ to city $$$B$$$ with cost $$$C$$$. Since everybody loves the capital city there is a fee for emotional damage that is charged to make a road away from the capital to $$$Y$$$: a road that has a distance $$$X$$$ from the capital will cost $$$X$$$ * $$$C$$$, $$$X$$$ is calculated by the number of roads in a simple path that exists between capital and $$$Y$$$. The capital city has number 1.

Calculate the minimum amount of money you need to spend to connect every city to the capital such that the distance from each city to the capital is minimal.

How can you pay for these roads if you are working for free? Why everybody loves the capital? Those are not the questions in this problem!

The first line, you will have two integers $$$N$$$ ($$$1 \leq N \leq 10^5$$$) and $$$M$$$ ($$$1 \leq M \leq 10^5$$$) representing the number of cities and the number of roads respectively. Each of the next $$$M$$$ lines contains three integers $$$A$$$, $$$B$$$ ($$$1 \leq A, B \leq N$$$)and $$$C$$$ ($$$1 \leq C \leq 10^5$$$) describing each of the road options you can possibly make.

Output a line with a single integer that represents the minimum cost it will take to connect all the cities to the capital, two cities are considered connected if there is a set of roads that you can use to reach from one city to another, it guaranteed that a solution exists.

5 4
1 2 10
1 3 4
1 4 12
1 5 1

27

5 5
1 2 10
1 3 4
2 3 8
5 4 12
1 5 1

39

5 4
1 2 10
2 3 4
3 4 12
4 5 1

58