가넷이나 버는 게 낫지 않아요?

석주는 게임 예능 '더 찌니어스'에 출연한다. 오늘 방송에서 하는 게임은 '징검다리'이고, 규칙은 다음과 같다.

1. 섬 $N$개와 양쪽 방향으로 건널 수 있는 다리 $M$개가 그려진 지도가 있다.
2. 다리마다 건너는 데 걸리는 시간이 정해져 있다.
3. 다리를 한 번 건널 때마다 그 다리에 걸린 만큼의 가넷을 받는다.
4. 모든 참가자는 1번 섬에서 출발하고, $N$번 섬에 도착한 순서대로 1등, 2등, ...의 순위를 받는다.
5. 1번 섬에서 $N$번 섬으로 가는 경로는 항상 존재한다.
6. 어떤 참가자가 건넌 다리의 순서와 완전히 같은 순서로 다른 참가자가 다리를 건널 수는 없다.

같은 섬을 여러 번 지나가도 되고, 같은 다리를 여러 번 건너도 된다.

석주는 같은 프로그램에 나오는 영석이와 몰래 연합을 맺었다. 오늘 석주는 영석이에게 1등을 넘기고 자신은 2등으로 들어오려고 한다. 공동 1등으로 도착한 경우도 2등으로 인정한다. 영석이는 가넷과 상관없이 1등만 하면 된다고 생각하지만, 석주는 개당 현금 100만 원의 가치가 있는 가넷을 최대한 많이 모으려고 한다. 두 사람은 다른 참가자보다 먼저 경로를 고른다.

석주는 남은 참가자 누구에게도 따라잡히면 안 된다. 그래서 1번 섬에서 $N$번 섬까지 가는 모든 이동 순서를 걸린 시간이 작은 것부터 늘어놓고, 두 번째 자리에 오는 시간에 도착한다. 걸린 시간이 같아도 건넌 다리의 순서가 다르면 서로 다른 자리를 차지한다. 석주는 그 시간에 도착하는 이동 순서 가운데 가넷을 가장 많이 받는 것을 고른다.

석주가 $N$번 섬에 도착하는 시간과 그때 모은 가넷의 수를 구하라.

첫 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 20$)가 주어진다.

각 테스트 케이스의 첫 줄에는 섬의 수 $N$ ($2 \le N \le 50\,000$)과 다리의 수 $M$ ($1 \le M \le 200\,000$)이 주어진다.

이어지는 $M$개의 줄에는 정수 $x$, $y$, $t$, $g$ ($1 \le x, y \le N$, $1 \le t, g \le 2^{31} - 1$)가 주어진다. $x$번 섬과 $y$번 섬을 잇는 다리가 있고, 이 다리를 건너는 데 $t$의 시간이 걸리며, 건널 때마다 가넷을 $g$개 받는다는 뜻이다. 같은 두 섬을 잇는 다리가 여러 개일 수 있다.

출력할 시간과 가넷의 수는 64비트 부호 있는 정수 범위에 들어간다.

각 테스트 케이스마다 한 줄씩 다음 형식으로 출력한다.

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

$i$는 1부터 시작하는 테스트 케이스 번호, $t$는 석주가 $N$번 섬에 도착하는 시간, $g$는 그때까지 모은 가넷의 수다.