Problem Statement

Every spring, the trail-running guild of Fennwick charters a great relay between the clubhouse at station 1 and the summit lodge at station n . The n stations are joined by m two-way trails, trail i linking stations u i and v i with a running time of w i seconds, and the trail map keeps every station reachable from every other. A relay route starts at station 1 , ends at station n , and may pass through any stations and trails along the way — runners are even allowed to double back and reuse a trail or revisit a station if they wish. The total time of a route is the sum of the running times of every trail crossing made, counted once per crossing. The guild's champion already holds the record for the fastest possible total time. To keep the rivalry alive, the vice-champion wants to chase a different mark: the smallest total time that is strictly greater than the fastest possible time. Given the trail map, find that runner-up time — the second-smallest distinct total time ove