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

석주는 유명한 게임 예능 ‘더 찌니어스’의 출연자다. 이 프로그램에서 오늘 ‘징검다리’라는 게임을 하려고 한다. 징검다리의 규칙은 다음과 같다:

1. N개의 섬과 M개의 양방향으로 통행이 가능한 다리가 그려진 지도가 있다.
2. 각 M개의 다리는 건너는데 걸리는 시간이 있다.
3. 각 M개의 다리는 건널 때마다 다리별로 정해진 가넷을 받게 된다.
4. 모든 플레이어는 1번 섬에서 게임을 시작하며, N번 섬에 도착한 순서대로 플레이어의 순위가 1등, 2등, …이 된다.
5. 1번 섬에서 N번 섬으로 가는 경로는 항상 존재한다.
6. 어떤 플레이어가 이용한 다리의 순서와 완전히 똑같은 순서로 다른 플레이어가 다리를 이용할 수 없다.

오늘의 방송에서 석주는 다른 ‘더 찌니어스’의 출연자인 영석이와 비밀스럽게 연합을 맺었다! 오늘 석주는 영석이에게 1등을 내어주고, 2등으로 들어오는 전략을 짜려고 한다. (단, 공동 1등인 경우 2등을 했다고 인정한다.) 영석이는 가넷과 관계 없이 1등만 하면 된다는 생각을 하는 반면, 석주는 개당 현금 100만원의 가치를 갖는 가넷을 최대한 많이 모으려고 한다. 영석이와 석주는 다른 플레이어보다 먼저 경로를 선택할 기회를 갖고 있다.

이러한 방법으로 플레이 했을 때, 석주가 2등으로 N번 섬에 도착할 때까지 걸리는 시간과 그 때 모을 수 있는 가넷의 수는 얼마나 될까? 

첫 번째 줄에는 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 섬의 수 N(1 ≤ N ≤ 50000)과 다리의 수 M(1 ≤ M ≤ 200,000)가 주어진다.

각 테스트 케이스의 두 번째 줄부터 M+1번 줄까지 32비트 정수 x, y, t, g (1 ≤ x, y ≤ N, t, g는 1보다 큰 32비트 부호 있는 정수)가 주어진다. 이는 x에서 y로 가는 다리가 있으며, 다리를 건너는 데에 걸리는 시간은 t, 얻을 수 있는 가넷의 수는 g임을 의미한다. 

i번째 테스트 케이스에서 석주가 t시간에 게임을 마치며 g가넷을 얻을 경우, “Game #i: Suckzoo ends game in time t, earning g garnet(s).”를 출력한다.