P1186 Marika

Mike got a new girlfriend, which made Marika very angry and eager to take revenge. Since she does not live in the same city as them, she starts preparing for a long trip. In this country, between any two cities there is at most one road, and we know the time needed to travel from one city to another. Mike happened to overhear that some road is under repair and is jammed, but he did not catch which road it is. No matter which single road is under repair, it is still possible to get from Marika’s city to Mike’s city. Marika will travel only on non-jammed roads, and she will follow a shortest route. Mike wants to know, in the worst case, how long it will take Marika to reach his city, so that he can make sure his new girlfriend is far enough away from that city. Write a program to help Mike find the maximum time (in minutes) that Marika needs to reach his city by a shortest route using only non-jammed roads.

The first line contains two space-separated integers $N$ and $M$, the number of cities and the number of roads, respectively. $1 \le N \le 1000$, $1 \le M \le N \times (N - 1)/2$. The cities are labeled $1 \sim N$, Mike is in city $1$, and Marika is in city $N$. Each of the next $M$ lines contains three space-separated integers $A, B, V$. Here $1 \le A, B \le N$, $1 \le V \le 1000$. These numbers mean there is a bidirectional road between city $A$ and city $B$, and it takes $V$ minutes to travel it.

Output a single line with the maximum time in minutes such that, no matter which single road is jammed, Marika can reach Mike within this time by a shortest route over non-jammed roads; if the time were any smaller, then there would exist some road which, once jammed, would prevent Marika from reaching Mike within that time.

Thanks to Imakf for providing three sets of hack testdata. Translated by ChatGPT 5