P2685 [TJOI2012] Bridge

There are $n$ islands and $m$ bridges. Each bridge connects two islands. There are some enemies on every bridge; the player can pass a bridge only after defeating the enemies on it, and doing so inflicts some damage to the player. There is also a big Boss guarding exactly one bridge, which is impassable for the player given their current ability. The Boss is evil and will choose a bridge to guard so that, after blocking that bridge, the minimum possible total damage the player must suffer to travel from island $1$ to island $n$ (of course the player will choose the path with the least damage) is as large as possible. Determine which bridges the Boss might guard. Note: **multiple edges** and **self-loops** are allowed.

The first line contains two integers $n, m$. The next $m$ lines each contain three integers $s, t, c$, indicating that the enemies on the bridge connecting islands $s$ and $t$ will inflict $c$ damage on the player.

One line with two integers $d, cnt$, where $d$ is the minimum damage the player must suffer in the presence of the Boss, and $cnt$ is the number of bridges that the Boss might guard.

- For $30\%$ of the testdata, $1 \le n \le 1000$. - For $100\%$ of the testdata, $1 \le n \le 100000$, $1 \le m \le 200000$, $1 \le c \le 10000$. - It is guaranteed that the player can reach island $n$ from island $1$. Translated by ChatGPT 5