시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 201 32 26 16.993%

문제

고대의 보물이 묻힌 동굴이 발견되었다.

보물의 가치는 어마어마해서 한 번 탐사하는 데 성공하면 세계 최고의 부자가 될 수 있을 만했다.

한 운 좋은 고고학 회사가 탐사의 전반적인 작업을 모두 맡게 되었다.

당신은 그 회사의 인턴으로 참여중이다.

지금까지의 작업 진척도는 다음과 같다.

  • 가영은 두 명의 프로젝트 총괄자 중 하나이며, 보석 감정의 대가이다. 가영이는 탐사할 동굴에 묻힌 모든 보물의 가치를 정리하는 데 성공했다.
  • 나희도 가영과 같은 프로젝트 총괄자이다. 나희는 모든 보물의 가치를 시장가치와 탐사 비용을 고려하여 동굴 하나당 어느 정도의 수익을 얻을 수 있을지 수치화하여 정리하였다.
  • 다미는 프로젝트 매니저의 자격으로 참가하였다. 다미는 동굴 탐사에 필요할 만한 모든 장비를 자체적인 판단에 따라 주문하였다. 하지만 탐사대원들과의 소통이 부족했던 탓에 다미가 주문한 탐사 기기 중 일부는 동굴에 들어갈 수 없을 정도로 커서 탐사 작업에 동원될 수가 없었다.
  • 그런 이유로 다미는 해고되었고, 라라가 새로 다미의 역할을 맡게 되었다. 라라는 다미가 주문했던 기기들이 탐사 작업에 동원될 수 있을 만큼 동굴을 넓힐 수 있는 장치들을 주문하였다. 그리고 탐사 작업이 끝난 후 탐사에 동원된 장비들을 회수할 추가적인 장비를 주문하는 것을 회사의 예산으로 해결할 수 있는지를 예산 총괄자에게 물어보았다.
  • 마리는 예산 총괄자이다. 마리는 라라가 장비를 끌어올릴 추가적인 장비를 회사의 예산으로 구매하는 데 반대하였고, 이것은 라라가 추가적인 장비를 도입하지 않기로 결정하는 데 큰 공헌을 하였다.
  • 여덟 시간에 걸친 기나긴 회의 끝에, 회사의 예산으로는 더 이상의 장비를 도입할 수 없을 것이라는 분석이 나왔다. 그래서 우선적으로 나희가 수치화한 이익에 따라 가장 많은 이익을 낼 동굴만을 탐사하고, 그 과정에 도입된 장비들은 그냥 동굴 안에 묻힌 채 버려두고 그 상태로 탐사권을 다른 회사에 팔기로 하였다.
  • 탐사권을 다른 회사에 판매하기 위해 경제학 전공의 바다가 고용되었다. 바다는 탐사 작업이 끝난 후 거래 전문가이자 바다의 언니인 사랑이와 상의해서 최대의 가치로 탐사권을 다른 회사에 판매할 예정이다.

당신은 프로젝트 매니저 가영이가 프로젝트 초창기에 고용한 기술자이다. 당신은 이제 나희가 수치화한 이익 수치에 따라 어느 동굴들을 탐사하는 것이 최대의 이익이 될 지 계산해야 한다. 동굴을 넓히거나 동굴을 탐사하는 데 드는 추가적인 비용은 이미 다미와 라라에 의해 계산되어 있다. 이를 모두 고려하여 각 동굴마다 얻을 수 있는 최대의 이익이 각 동굴마다 수치화되어 주어질 것이다. 동굴의 지도는 아영이를 리더로 한 탐사대원들에 의해 이미 완성되어 있기 때문에 정확도는 100%에 달한다.

이제 순차적으로 탐사할 수 있는 순서대로 한 동굴에서 얻을 수 있는 손실과 이득을 계산하여 종합한 이익 표가 당신에게 주어진다. 처음으로 탐사해야만 하는, 입구의 역할을 하는 동굴은 항상 첫 번째 동굴이며, 다른 동굴들은 주어진 순서대로만 탐사할 수 있다. 어떤 동굴에서 탐사를 끝낸 뒤 이전 동굴로 장비를 다시 돌려놓는 데 필요한 추가적인 장비는 마리의 결정에 의해 도입하지 않기로 하였기에, 한 번 동굴에 입장하면 이제 그 동굴보다 깊이 있으며 서로 직접 연결된 동굴들로만 탐사를 진행할 수 있다.

입력

입력의 첫 줄엔 테스트 케이스의 수 T가 주어진다. (1 ≤ T ≤ 10)

각 테스트 케이스의 첫 줄엔 탐사할 수 있는 동굴의 수 N과 서로 직접 연결된 동굴 쌍의 수 E가 주어진다. (1 ≤ N ≤ 2 · 10 4; 0 ≤ E ≤ 105)

그리고 바로 다음 줄에 N개의 정수 v 1, v2, ... , vN이 주어진다. 이는 각 동굴을 탐사해서 얻을 수 있는 보물의 가치를 수치화한 것이다. (0 ≤ vi ≤ 104)

이후 E줄에 걸쳐 세 정수 a e be ce가 주어진다. 이는 동굴 ae가 be와 직접 연결되어 있으며, 동굴을 넓히고 작업 장비를 be에 들여놓는 데에 ce만큼의 작업 비용이 든다는 것을 의미한다. (1 ≤ ae, be ≤ N; 0 ≤ ce ≤ 104)

항상 탐사의 시작은 1번 동굴이다. 1번 동굴을 탐사하지 않고서는 다른 동굴에 입장하는 것이 불가능하다.

출력

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

첫 줄엔 동굴을 탐사함으로써 얻을 수 있는 최대 이익과 그 때 방문한 동굴의 수를 출력하고,

두 번째 줄엔 그 이익을 얻을 수 있는 경로를 방문 순으로 출력한다.

이 때, 그 이익을 얻을 수 있는 경로가 여러 개라면 아무 것이나 출력하면 된다.

예제 입력

3
1 0
10
4 3
10 20 30 40
1 2 19
1 3 23
1 4 34
4 4
10 20 30 40
1 2 10
2 4 20
1 3 20
3 4 10

예제 출력

10 1
1
17 2
1 3
50 3
1 3 4

힌트

출처

ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > German Collegiate Programming Contest > GCPC 2014 D번