놀이터의 은신처

어린 티미는 놀이터를 좋아합니다. 특히 널빤지 다리와 밧줄로 이어진 복잡한 나무 탑, 미끄럼틀과 밧줄 사다리가 있는 놀이터를 가장 좋아합니다. 부모님이 허락만 한다면 며칠이고 놀 수 있을 텐데, 언젠가 부모님은 집에 갈 시간이라고 말합니다. 그래서 티미는 다음 나들이를 위한 계획을 세웠습니다. 아버지가 그냥 자신을 붙잡게 두지 않고, 가장 복잡한 구조물에서 가장 높은 플랫폼까지 올라가 그곳에 숨는 것입니다. 그러면 아버지가 잡기 어려워져 시간을 조금이라도 벌 수 있습니다.

모험 놀이터는 여러 개의 플랫폼으로 이루어져 있습니다. 각 플랫폼을 지면에서 곧바로 오르는 난이도는 플랫폼마다 다릅니다. 또한 플랫폼들은 난이도가 서로 다른 다리로 연결되어 있으며, 미끄럼틀처럼 한 방향으로는 반대 방향보다 훨씬 쉽게 지날 수 있는 연결도 있습니다.

놀이터의 배치도가 주어질 때, 지면에서 도달하기 가장 어려운 플랫폼을 찾으세요. 경로의 난이도는 그 경로에서 사용한 연결들의 난이도의 합이고, 한 플랫폼에 도달하는 난이도는 지면에서 그 플랫폼에 이르는 가장 쉬운(난이도가 가장 낮은) 경로의 난이도입니다.

첫 줄에는 테스트 케이스의 수 $n$이 주어집니다.

각 테스트 케이스의 첫 줄에는 두 정수 $p$와 $c$ ($1 \le p, c \le 10000$)가 주어지며, 각각 플랫폼의 수와 연결의 수입니다. 다음 줄에는 $p$개의 정수가 주어지며, 그중 $i$번째 값 $d_i$ ($0 \le d_i \le 1000$)는 플랫폼 $i$를 지면에서 곧바로 오르는 난이도입니다.

이어지는 $c$개의 줄은 각각 하나의 연결을 네 정수 $i$, $j$, $a$, $b$ ($i < j$)로 나타냅니다. $i$와 $j$는 연결된 두 플랫폼의 0-기반 번호이고, $a$ ($0 \le a \le 1000$)는 플랫폼 $i$에서 플랫폼 $j$로 가는 난이도, $b$ ($0 \le b \le 1000$)는 플랫폼 $j$에서 플랫폼 $i$로 가는 난이도입니다. 같은 두 플랫폼 사이에 연결이 여러 개 있을 수 있습니다.

각 테스트 케이스마다 먼저 Scenario #i:를 한 줄에 출력합니다. 여기서 $i$는 1부터 세는 테스트 케이스 번호입니다. 그다음 줄에 지면에서 도달하기 가장 어려운 플랫폼의 0-기반 번호를 출력합니다. 도달 난이도가 같은 플랫폼이 둘 이상이면 그중 가장 작은 번호를 출력합니다. 연속한 두 테스트 케이스 사이는 빈 줄로 구분합니다.