Bessie tổ chức đại hội bò hằng năm toàn quốc, muốn chọn nơi tiện nhất.

Mỗi bò sống trong một nhà kho trong $N$ ($1 \le N \le 100,000$) kho số $1..N$, nối $N-1$ đường để từ mọi nhà đến mọi nhà. Đường $i$ nối $A_{i}$ và $B_{i}$ ($1 \le A_i \le N; 1 \le B_i \le N$), dài $L_{i}$ ($1 \le L_{i} \le 1,000$). Bất kỳ nhà trong $N$ đều tổ chức được; nhà $i$ có $C_{i}$ ($0 \le C_{i} \le 1,000$) bò.

Tiện nhất tức bất tiện nhỏ nhất. Ở $X$, bất tiện là tổng quãng đường mọi bò tới $X$. Nếu từ $i$ đến $X$ là 20 thì tổng $C_{i}*20$. Chọn nơi tốt nhất.

Năm nhà có số bò khác nhau trong ngoặc vuông, đường dài khác nhau. 3 và 4 không có bò.

      1     3     4     5
      @--1--@--3--@--3--@[2]
     [1]    |
            2
            |
            @[1]
            2

Có thể bất kỳ nhà nào; bảng bất tiện, B1–B5 các nhà, cột cuối tổng.

Nếu tổ chức ở 1, từng nhà:

• Nhà 1: 0, không đi!
• Nhà 2: 3, đường $2+1=3$ nhân 1 bò ra 3.
• Nhà 3: 0, không bò!
• Nhà 4: 0, không bò!
• Nhà 5: 14, đường $3+3+1=7$ nhân 2 bò ra 14.

Tổng bất tiện 17.

Tốt nhất 15 tại 3, 4 hoặc 5.

Dữ liệu vào

• Dòng 1: số nguyên $N$.
• Dòng $2..N+1$: dòng $i+1$, số nguyên $C_{i}$.
• Dòng $N+2..2N$: dòng $i+N+1$, ba số nguyên $A_{i}$, $B_{i}$, $L_{i}$.

Dữ liệu ra

• Dòng 1: bất tiện nhỏ nhất có thể.

Ví dụ

Dữ liệu vào 1

5
1
1
0
0
2
1 3 1
2 3 2
3 4 3
4 5 3

Dữ liệu ra 1

15

Tác giả: Jeffrey Wang, từ một cuộc thi, 2010