마지막 버스의 표지 점검

문제

어느 지역의 버스 운영팀은 운행이 끝난 뒤 작은 점검 차량으로 정류장의 안내 표지를 확인한다. 지역에는 1번부터 N번까지 번호가 붙은 정류장이 있다. 정류장 사이를 잇는 도로는 N−1개이며, 모든 정류장 사이를 도로를 따라 이동할 수 있다. 따라서 두 정류장 사이에서 같은 정류장을 반복하지 않고 이동하는 경로는 정확히 하나다. 각 도로는 양방향으로 이동할 수 있으며 도로마다 정해진 이동 시간이 든다. 같은 도로를 여러 번 지나면 지날 때마다 그 시간이 다시 든다. 차량이 도로 중간에서 방향을 바꾸거나, 도로에 연결되지 않은 두 정류장 사이를 직접 이동하는 것은 허용되지 않는다. 이동 시간은 차량이 어느 방향으로 도로를 지나는지와 관계없이 같다. 운영팀은 표지 점검이 필요한 정류장을 미리 표시했다. 점검 차량은 반드시 1번 정류장에서 출발하여 표시된 정류장을 모두 한 번 이상 방문한 뒤, 다시 1번 정류장으로 돌아와야 한다. 표시되지 않은 정류장을 지나거나 여러 번 방문해도 된다. 표시된 정류장의 방문 순서는 자유롭게 정할 수 있으며, 표지를 확인하는 데 걸리는 시간은 전체 이동 시간에 포함하지 않는다. 1번 정류장도 점검 대상으로 표시될 수 있다. 이 경우 출발할 때 해당 정류장의 점검을 마친 것으로 본다. 점검 대상으로 표시된 정류장이 전혀 없거나, 1번 정류장만 표시되었다면 차량은 이동하지 않고 작업을 마칠 수 있다. 이때 필요한 이동 시간은 0이다. 운영팀은 도로를 지나는 횟수를 줄여 점검 차량의 총이동 시간을 최소화하려 한다. 서로 다른 이동 순서가 같은 최소 시간을 만들 수 있지만, 실제 방문 순서는 출력하지 않는다. 도로의 연결 관계와 이동 시간, 점검 대상 표시가 주어질 때 모든 조건을 만족하는 최소 총이동 시간을 구해야 한다.

입력

첫째 줄에 정류장 수 N이 주어진다. 둘째 줄에 N개의 정수 c1,…,cN이 주어진다. ci가 1이면 i번 정류장이 점검 대상이고, 0이면 점검 대상이 아니다. 다음 N−1개 줄에 도로의 양 끝 정류장 u, v와 이동 시간 w가 주어진다. 모든 수는 정수이며 1≤N≤15000, ci∈{0,1}, 1≤u,v≤N, u≠v, 1≤w≤99이다. 주어진 도로는 트리를 이룬다. N=1이면 도로 정보는 주어지지 않는다.

출력

1번 정류장에서 출발하여 모든 점검 대상 정류장을 방문하고 1번 정류장으로 돌아오는 최소 총이동 시간을 정수 하나로 출력한다. 이동이 필요 없으면 0을 출력한다.

6
0 0 1 0 1 0
1 2 3
2 3 4
2 4 2
4 5 6
1 6 8

30

1
1

0

4
0 0 0 0
1 2 7
2 3 8
2 4 9

0

출처: Devin.KR 자체 제작