American Tour
InterviewTime limit1sMemory limit256 MB
Find the shortest walk from node 1 to node N that passes through node 2, where no road may be repeated but nodes may be revisited.
- Level
Medium5 of 10
- Topics
- Graph, Shortest path, Implementation
- Solved
- No attempts yet
Problem
Seunghan decided to visit the United States for the first time this year to celebrate his graduation.
Before leaving, Seunghan looked up N important locations for his trip: tourist attractions, hotels, airports, and so on.
These N locations are numbered 1, 2, ..., N, and they are connected by M roads in total.
Every road can be traveled in both directions, and multiple roads may connect the same pair of locations.
After arriving in the United States, Seunghan wants to see the Statue of Liberty, which he had only heard about, so he plans to visit it and then head to his lodging.
Seunghan also wants to see many things, so while traveling from the Statue of Liberty to his lodging, he will not use the same road more than once. Visiting the same location multiple times is allowed.
Seunghan starts at location 1, the Statue of Liberty is location 2, and his lodging is location N.
Given the map of the United States, find the length of the shortest route for Seunghan to pass through the Statue of Liberty and reach his lodging under these conditions.
Passing by the lodging on the way to the Statue of Liberty is allowed, and at least one route satisfying Seunghan's conditions is guaranteed to exist.
Input
The first line gives the number of locations N and the number of roads M. (3 ≤ N ≤ 1000, 2 ≤ M ≤ 10000)
The next M lines give the numbers of the locations the road connects, si, ei, and the length of the road, di. (1 ≤ si, ei ≤ N, 1 ≤ di ≤ 10000)
Location 1 is Seunghan's starting point, location 2 is the Statue of Liberty, and location N is his lodging.
Output
Print the length of the shortest route from the starting point to the lodging that passes through the Statue of Liberty.