The Runner-Up Relay Route - Google Online Assessment

Problem Preview

"Every spring, the trail-running guild of Fennwick charts the 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 over all possible relay routes from station 1 to station n. **Function Description** Implement the function `findSecondShortestTime`. **Parameters** * **n:** the number of stations. * **m:** the number of trails. * **arr:** 2D with m number of rows and 3 columns: * **u:** u[i] is one endpoint of trail i. * **v:** v[i] is the other endpoint of trail i. * **w:** w[i] is the running time of trail i in seconds. **Returns** Returns the second-smallest distinct total time of a route from station 1 to station n. **Input Format** * The first line contains a single integer n, the number of stations. * The second line contains a single integer m, the number of trails. * Each of the next m lines contains three integers u_i v_i w_i describing a trail. **Output Format** * Print a single integer — the second-smallest distinct total route time in seconds. **Constraints** * 3 ≤ n ≤ 100000 * n - 1 ≤ m ≤ 200000 * 1 ≤ u_i, v_i ≤ n, u_i ≠ v_i * 2 ≤ w_i ≤ 1000000000 * The trail network is connected; multiple trails may join the same pair of stations. * Routes may revisit stations and reuse trails; a runner-up time always exists. * All values are integers. --- ### Sample Input 1 ```text 4 4 1 2 3 2 4 4 1 3 2 3 4 6 ``` ### Sample Output 1 ```text 8 ``` **Explanation** Routes from station 1 to station 4 and their total times: 1 -> 2 -> 4: 3 + 4 = 7 seconds. 1 -> 3 -> 4: 2 + 6 = 8 seconds. 1 -> 2 -> 1 -> 2 -> 4: 3 + 3 + 3 + 4 = 13 seconds, and longer doubling-back routes cost even more. The fastest time is 7. Among all total times {7, 8, 13, ...}, the smallest value strictly greater than 7 is 8. Note: Your code must be able to print the sample output from the provided sample input. However, your code is run against multiple hidden test cases. Therefore, your code must pass these hidden test cases to solve the problem statement. --- ### Sample Input 2 ```text 3 3 1 2 5 2 3 5 1 3 4 ``` ### Sample Output 2 ```text 10 ```"