| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 50 | 30 | 29 | 59.184% |
The ICPC Kingdom is a big kingdom with $N$ cities, numbered from 1ドル$ to $N$. The charm of the ICPC Kingdom lies in its beautiful sceneries in the kingdom. To promote those sceneries, the King of the ICPC Kingdom decided to make $M$ toll roads, numbered from 1ドル$ to $M,ドル near the scenic views for the tourists to enjoy. To use toll road $i$ that connects city $U_i$ to $V_i$ bidirectionally, one must pay $W_i$. It is possible to travel from one city to any other city using these toll roads.
Although those toll roads have been built and can be used, they still do not attract tourists. The King decided to make a promotion, where one can pay in advance for the toll roads they want to use and can use it multiple times as long as they do not leave the ICPC Kingdom.
This idea can finally attract tourists, but there’s a strange behaviour happening. All of the tourists only pay for the set of toll roads that gives the minimum total pay which allows them to travel from one city to any other city regardless of the distance. Interestingly, such a set of toll roads is unique under current toll pricing. This strange behaviour does not fully expose the kingdom’s scenery to the tourists.
To promote more scenery, the King decided to increase the price of some toll roads. If toll road $i$ is used by the tourists’ strange behaviour before the toll price increase, then after the price increase, the King must ensure toll road $i$ is not used by the tourists’ strange behaviour. For stability, the King also wants the total price increase across all toll roads to be as small as possible.
The King asked you to calculate what is the minimum total price increase to fulfill the King’s plan or report that it is impossible to do so.
Input begins with two integers $N$ $M$ (2ドル ≤ N ≤ 100,円 000$; $N - 1 ≤ M ≤ 200,円 000$) representing the number of cities and toll roads. Each of the next $M$ lines contains 3ドル$ integers $U_i$ $V_i$ $W_i$ (1ドル ≤ U_i < V_i ≤ N$; 1ドル ≤ W_i ≤ 10^9$) representing toll i that connects city $U_i$ and $V_i$ with price $W_i$. There exists a unique set of toll roads that allow travel between any two cities with minimum total pay before the price increase.
If the King’s plan is possible to achieve, then output an integer representing the minimum total increase to fulfill the King’s plan. Otherwise, output -1 in a single line.
4 6 1 2 2 1 3 5 1 4 5 2 3 3 2 4 5 3 4 4
9
Before the price increase, the tourists will choose toll roads 1ドル,ドル 4ドル,ドル and 6ドル$ to travel. By increasing the price of toll roads 1ドル,ドル 4ドル,ドル and 6ドル,ドル to 6ドル,ドル the tourists will use toll roads 2ドル,ドル 3ドル,ドル and 5ドル$ to travel. Total increase toll roads is $(6 - 2) + (6 - 3) + (6 - 4) = 9$.
3 4 1 2 3 2 3 4 1 3 5 1 3 10
-1
Before the price increase, the tourists will choose toll roads 1ドル$ and 2ドル$. No matter how many the price increase, the tourists will always choose at least one of those two toll roads.
5 10 1 2 14 1 3 14 1 4 9 1 5 15 2 3 8 2 3 10 2 4 13 3 4 8 4 5 10 4 5 15
21