Description

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.

Input Format

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.

Output Format

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.

3 4
1 2 1
1 2 2
2 3 1
2 3 2

3 2

Hint

• 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