| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 129 | 69 | 64 | 52.893% |
There are $n$ cities in Asia-Pacific, numbered from 1ドル$ to $n$. The 2024 ICPC Asia Pacific Championship is held in Hanoi, which is city $n$.
There are $m$ bidirectional roads, numbered from 1ドル$ to $m,ドル connecting some pairs of cities. Road $i$ connects cities $u_i$ and $v_i$ and takes $t_i$ units of time to travel in either direction. Each road connects different cities and different roads connect different pairs of cities.
You live in city 1ドル$. You would like to travel to city $n$ to attend the contest through a sequence of roads, and then travel back to city 1ドル$ through a sequence of roads. Traveling through the same route is boring, so you would like the routes in both traversals to be different. Two routes are considered different if the set of distinct roads traversed through one route is different from the set of distinct roads traversed through the other route.
In each traversal, it is possible to pass through the same city or road multiple times. It is also possible to continue traversing after reaching the destination city (i.e., city 1ドル$ or city $n$). The traversal time is the sum of the travel times of the roads passed through in the traversal. If a road is passed through multiple times in the traversal, then the travel time of the road is also counted multiple times accordingly.
Determine the minimum total traversal time to do both traversals satisfying the requirements above, or indicate if the requirements cannot be satisfied.
The first line of input contains two integers $n$ and $m$ (2ドル ≤ n ≤ 100,円 000$; 1ドル ≤ m ≤ \min(\frac{n(n-1)}{2}, 300,円 000)$). Each of the next m lines contains three integers. The $i$-th line contains $u_i,ドル $v_i,ドル and $t_i$ (1ドル ≤ u_i < v_i ≤ n$; 1ドル ≤ t_i ≤ 1000$). Different roads connect different pairs of cities.
Output an integer representing the minimum total traversal time to do both traversals satisfying the requirements above, or -1 if the requirements cannot be satisfied.
3 2 1 2 10 1 3 5
30
The cities and roads are illustrated by Figure J.1.
Figure J.1: Illustration of sample input #1.
One possible way to minimize the total traversal time is as follows:
It can be shown that there is no way to do both traversals with a smaller total traversal time.
4 3 1 2 10 2 3 5 3 4 2
-1
The cities and roads are illustrated by Figure J.2.
Figure J.2: Illustration of sample input #2.
To go from city 1ドル$ to city 4ドル$ and then back, both traversals have to pass through all the roads. Therefore, it is impossible to satisfy the requirements above.
4 4 1 2 3 2 4 2 1 3 3 3 4 4
12
3 1 1 2 1000
-1