Farmer John tìm ra bí quyết làm bơ ngọt nhất Wisconsin: đường. Đặt viên đường ở đồng cỏ, ông biết $N$ bò ($1\le N\le500$) sẽ liếm và cho bơ siêu ngọt bán giá cao hơn. Dĩ nhiên tiền thêm mua đồ xa xỉ cho bò.

FJ khôn khéo. Như Pavlov ngày xưa, ông biết huấn luyện bò đi tới một đồng khi nghe chuông. Ông đặt đường ở đó và rung giữa buổi chiều để lần vắt sữa tối cho sữa hoàn hảo.

Mỗi bò ở đồng cho trước, không nhất thiết một mình. Từ vị trí và đường nối, tìm đồng đặt đường để tổng quãng đường khi chuông rung nhỏ nhất. Các đồng đủ kết nối để luôn có lời giải.

Dữ liệu vào

• Dòng $1$: số nguyên cách bằng dấu cách, số bò $N$, đồng $P$ ($2\le P\le800$), đường $C$ ($1\le C\le1{,}450$). Bò có số duy nhất $1\ldots N$, đồng $1\ldots P$.

• Dòng $2\ldots N+1$: số nguyên là đồng bò ăn cỏ; bò $i$ ở dòng $i+1$.

• Dòng $N+2\ldots N+C+1$: ba số nguyên cách bằng dấu cách, hai đồng và độ dài. Đường hai chiều, mỗi cặp tối đa một đường trực tiếp. Hai số đầu trong $1\ldots P$, số ba trong $1\ldots225$.

Dữ liệu ra

• Dòng $1$: số nguyên là tổng quãng đường nhỏ nhất bò tới đồng đặt đường.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

8

Ghi chú

Sơ đồ thể hiện các nối bằng hình học:

          P2  
 P1 @--1--@ C1
     \    |\
      \   | \
       5  7  3
        \ |   \
         \|    \ C3
       C2 @--5--@
          P3    P4

Đặt tại $4$, bò $1$ đi $3$ đơn vị, bò $2$ đi $5$, bò $3$ đi $0$, tổng $8$.

Tác giả bài toán: Greg Galperin, 2001