고대 동굴 탐사

고대의 보물이 묻힌 동굴이 발견되었다. 보물의 가치는 어마어마해서, 한 번만 탐사에 성공해도 세계 최고의 부자가 될 만하다. 운 좋은 고고학 회사 하나가 탐사 작업 전체를 맡았고, 당신은 그 회사의 인턴이다.

지금까지의 진척은 다음과 같다.

• 가영은 두 명의 프로젝트 총괄자 중 하나이며 보석 감정의 대가이다. 가영은 탐사할 동굴에 묻힌 모든 보물의 가치를 정리했다.
• 나희도 가영과 같은 프로젝트 총괄자이다. 나희는 시장가치와 탐사 비용을 함께 따져서 동굴 하나마다 얻을 수 있는 수익을 수치로 정리했다.
• 다미는 프로젝트 매니저로 참가했다. 다미는 동굴 탐사에 필요할 만한 장비를 모두 자기 판단으로 주문했다. 그런데 탐사대원과 소통이 부족해서, 주문한 기기 중 일부는 동굴에 들어가지 못할 만큼 커서 탐사에 쓸 수 없었다.
• 그 일로 다미는 해고되고 라라가 그 역할을 맡았다. 라라는 다미가 주문한 기기가 들어갈 수 있도록 동굴을 넓히는 장치를 주문했다. 그리고 탐사가 끝난 뒤 장비를 회수할 추가 장비를 회사 예산으로 살 수 있는지 예산 총괄자에게 물었다.
• 마리는 예산 총괄자이다. 마리는 장비를 끌어올릴 추가 장비를 회사 예산으로 사는 데 반대했고, 라라는 추가 장비를 들이지 않기로 결정했다.
• 여덟 시간에 걸친 긴 회의 끝에, 회사 예산으로는 장비를 더 들일 수 없다는 분석이 나왔다. 그래서 나희가 수치화한 이익에 따라 가장 많은 이익을 낼 동굴만 탐사하고, 그 과정에 들인 장비는 동굴 안에 그대로 버려둔 채 탐사권을 다른 회사에 팔기로 했다.
• 탐사권을 팔기 위해 경제학 전공의 바다가 고용되었다. 바다는 탐사가 끝난 뒤 거래 전문가인 언니 사랑과 상의해서 탐사권을 가장 높은 값에 팔 예정이다.

당신은 가영이 프로젝트 초기에 고용한 기술자이다. 이제 나희가 수치화한 이익에 따라 어느 동굴을 탐사해야 이익이 가장 큰지 계산해야 한다. 동굴을 넓히거나 탐사하는 데 드는 추가 비용은 다미와 라라가 이미 계산해 두었다. 동굴 지도는 아영을 리더로 한 탐사대가 완성했으므로 정확도는 100%이다.

탐사는 언제나 입구 역할을 하는 1번 동굴에서 시작한다. 1번 동굴을 탐사하지 않고 다른 동굴에 들어가는 것은 불가능하다. 어떤 동굴의 탐사를 끝낸 뒤 장비를 더 얕은 동굴로 되돌릴 추가 장비는 마리의 결정으로 들이지 않았다. 그래서 한 동굴에 들어가면 그 동굴보다 깊이 있으면서 직접 연결된 동굴로만 탐사를 이어갈 수 있다. 탐사 경로는 1번 동굴에서 출발해 점점 깊어지는 한 줄기 길이 된다.

동굴 $i$를 탐사하면 $v_i$만큼의 이익을 얻는다. 동굴 $a$에서 직접 연결된 동굴 $b$로 넘어가려면 동굴을 넓히고 장비를 옮기는 데 $c$만큼의 비용이 든다. 총 이익은 탐사한 동굴의 가치 합에서 지나간 통로의 비용 합을 뺀 값이다. 탐사는 어느 동굴에서든 그만둘 수 있고, 1번 동굴만 탐사하고 끝내도 된다.

모든 동굴은 1번 동굴에서 도달 가능하다.

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

각 테스트 케이스의 첫 줄에 탐사할 수 있는 동굴의 수 $N$과 서로 직접 연결된 동굴 쌍의 수 $E$가 주어진다. ($1 \le N \le 2 \times 10^4$, $0 \le E \le 10^5$)

다음 줄에 $N$개의 정수 $v_1, v_2, \dots, v_N$이 주어진다. $v_i$는 동굴 $i$를 탐사해서 얻는 보물의 가치이다. ($0 \le v_i \le 10^4$)

이어지는 $E$개의 줄에 세 정수 $a_e$, $b_e$, $c_e$가 주어진다. 동굴 $a_e$가 동굴 $b_e$와 직접 연결되어 있고, 동굴을 넓혀 작업 장비를 $b_e$로 들여놓는 데 $c_e$만큼의 비용이 든다는 뜻이다. ($1 \le a_e, b_e \le N$, $0 \le c_e \le 10^4$)

입력에서 $b_e$는 항상 $a_e$보다 깊이 있는 동굴이다. 동굴 번호는 깊이 순서와 일치하지 않는다. 같은 동굴 쌍이 비용만 다른 채로 여러 번 주어질 수 있다.

탐사의 시작은 항상 1번 동굴이고, 모든 동굴은 1번 동굴에서 도달 가능하다.

각 테스트 케이스마다 두 줄을 출력한다.

첫 줄에는 탐사로 얻을 수 있는 최대 이익과, 그 이익을 얻을 때 탐사한 동굴의 수를 공백으로 구분해 출력한다.

둘째 줄에는 그 이익을 얻는 탐사 경로를 방문 순서대로 공백으로 구분해 출력한다.

최대 이익을 얻는 경로가 여러 개라면 동굴 번호 수열이 사전순으로 가장 앞서는 경로를 출력한다. 두 수열을 비교할 때는 앞에서부터 번호를 차례로 견주고, 한쪽이 다른 쪽의 앞부분과 완전히 같다면 짧은 쪽이 앞선다.