Wouldn't it be better to just earn garnets?

Suckzoo is a contestant on the game show The Zzinius. Today's episode plays a game called Stepping Stones, and the rules are these.

1. A map shows $N$ islands and $M$ bridges, and every bridge can be crossed in both directions.
2. Each bridge takes a fixed amount of time to cross.
3. Every time a player crosses a bridge, that player receives the number of garnets attached to that bridge.
4. Every player starts on island 1, and players are ranked 1st, 2nd, ... in the order they reach island $N$.
5. A route from island 1 to island $N$ always exists.
6. No player may cross bridges in exactly the same order as another player.

A player may pass through the same island many times and cross the same bridge many times.

Suckzoo has secretly allied with Youngseok, another contestant on the show. Today Suckzoo hands 1st place to Youngseok and takes 2nd place himself. Arriving tied for 1st place also counts as 2nd place. Youngseok only wants 1st place and does not care about garnets, while Suckzoo wants as many garnets as possible, because one garnet is worth a million won in cash. The two of them choose their routes before any other player.

None of the remaining players may overtake Suckzoo. So take every bridge order that leads from island 1 to island $N$ and sort those orders by total crossing time. Two orders that cross different bridges take two separate places even when their total time is equal. Suckzoo arrives at the second time on that list, and among the bridge orders that finish at that time he picks one that pays the most garnets.

Find the time at which Suckzoo reaches island $N$ and the number of garnets he has collected by then.

The first line has the number of test cases $T$ ($1 \le T \le 20$).

The first line of each test case has the number of islands $N$ ($2 \le N \le 50\,000$) and the number of bridges $M$ ($1 \le M \le 200\,000$).

Each of the next $M$ lines has four integers $x$, $y$, $t$, $g$ ($1 \le x, y \le N$, $1 \le t, g \le 2^{31} - 1$). A bridge joins island $x$ and island $y$, crossing that bridge takes time $t$, and every crossing pays $g$ garnets. More than one bridge may join the same pair of islands.

The time and the garnet count you print fit in a signed 64-bit integer.

For each test case, print one line in this format.

Game #i: Suckzoo ends game in time t, earning g garnet(s).

Here $i$ is the test case number starting at 1, $t$ is the time Suckzoo reaches island $N$, and $g$ is the number of garnets he has collected by then.