보도블록 10계명

문제 정보

문제

세울시의 보도블록 공사는 생각도 계획도 꿈도 희망도 없기로 유명합니다. 사시사철 일정한 양의 공사에 시민들은 수없이 많은 민원을 제기했지만, 지금까진 아무런 변화가 없었습니다. 그러나 재작년에 새로 부임한 “박스나” 세울시장은 이에 대한 대책 마련이 필요하다고 보고, 세울시에 있는 모든 구청에 공사가 필요한 보도블록을 미리 조사하도록 지시했습니다.

그런데 모든 구청의 보도블록 조사가 끝난 후, 한 가지 문제점이 발견되었습니다. 구 내의 보도블록은 해당 구청의 예산으로 공사를 하면 되지만, 구와 구를 잇는 보도블록은 어느 구청 예산으로 공사를 할 지 애매했던 것입니다. 고민에 고민을 거듭하던 박스나 세울시장은 모든 구청에 차별없이 같은 액수의 예산을 지원하기로 결정하고, 구와 구를 잇는 보도블록은 연결된 두 구가 함께 비용을 내도록 지시했습니다. 예산이 부족한 구는 적게 내고, 남는 구는 많이 내는 식으로 어찌됐든 양쪽 구의 예산으로 공사를 할 수 있으면 됩니다. 그리고 공사에 필요한 총 금액을 계산하기 위해, 알고스팟의 유능한 프로그래머인 바로 당신을 고용했습니다.

각 구 내의 보도블록 공사비용과 구와 구를 잇는 보도블록 공사비용 정보가 주어질 때, 모든 공사를 할 수 있는 최소 예산을 계산하세요. 세울시의 모든 구청은 구에 인접한 보도블록에 예산을 지원할 때, 0 이상의 정수만큼 지원합니다.

입력

입력의 첫 줄에는 테스트 케이스의 수 C가 주어집니다. 각 테스트 케이스의 첫 줄에는 세울시에 있는 모든 구의 수 N이 주어집니다. 두 번째 줄에는 i번 구 내의 보도블록 공사비용 Ai가 주어집니다. 세 번째 줄에는 구와 구를 잇는 보도블록의 수 M이 주어집니다. 그 후 M줄에 각각의 보도블록이 연결된 두 구의 번호 Vj, Uj와 공사비용 Bj가 주어집니다. Vj와 Uj는 서로 다른 수고, 같은 (Vj, Uj) 혹은 (Uj, Vj) 쌍이 두 번 이상 주어지지 않습니다. 입력으로 주어진 M개의 보도블록으로 세울시를 연결하면 하나의 연결 그래프가 됩니다. 즉, 어떤 구에서 다른 구로 가는 경로가 항상 하나 이상 존재합니다.

출력

각 테스트 케이스마다 한 줄에 세울시가 보도블록 공사를 위해 지원해야 되는 총 예산의 액수를 출력하세요.

예제 입력

2
3
3 4 1
2
1 2 7
2 3 5
5
1 1 1 1 1
5
1 2 3
1 3 2
3 4 7
2 3 5
5 2 2

예제 출력

21
30

노트

2 ≤ N ≤ 50
1 ≤ M ≤ N * (N-1) / 2
1 ≤ Vj, Uj ≤ N
Vj != Uj
0 ≤ Ai, Bj ≤ 1,000

2개의 댓글이 있습니다.