화물차 수거 경로

한 운송 회사는 지점 1에 있고, 트리 형태의 도로망에 있는 고객 지점들의 짐을 모두 수거하려고 한다. 트리에서는 두 지점 사이의 경로가 항상 하나뿐이다.

회사는 최대 10톤을 실을 수 있는 화물차 한 대를 사용한다. 각 고객의 짐은 정수 톤 단위로 나누어 실을 수 있다. 화물차는 지점 1에서 출발하고, 한 번 운행할 때 여러 고객 지점을 들를 수 있지만 싣는 짐의 총량은 10톤을 넘을 수 없다. 운행을 마치면 반드시 지점 1로 돌아와 짐을 내려놓는다.

모든 짐을 수거해 지점 1로 돌아오기 위해 필요한 총 주행거리가 최소가 되도록 운행 계획을 출력하시오.

첫 줄에 지점의 개수 n이 주어진다. n은 50 이하이다.

다음 n - 1개의 줄에는 지점 2, 지점 3, ..., 지점 n에 있는 짐의 무게가 차례대로 하나씩 주어진다.

그 다음 n - 1개의 줄에는 서로 인접한 두 지점 i, j와 그 사이의 거리 d가 주어진다. 모든 짐의 무게와 거리는 정수이다.

nw2w3...wni1 j1 d1i2 j2 d2...in-1 jn-1 dn-1

첫 줄에 최소 총 주행거리 D를 출력한다.

그 다음 줄부터는 실제 운행 계획을 출력한다. 짐을 싣는 순서대로 지점 번호와 싣는 무게를 한 줄에 출력한다. 한 번의 운행을 마치고 지점 1로 돌아오면 그 줄에는 1만 출력한다. 모든 출력 무게는 정수이며, 한 번의 운행에서 싣는 총량은 10을 넘을 수 없다.

Di1.1 w1.1...i1.k1 w1.k11i2.1 w2.1...1...