Farmer John đi thuyền tìm kho báu huyền thoại trên một trong $N$ đảo $(1 \le N \le 100)$ ở Cowribbean Sea, đánh số $1,\ldots,N$.

Bản đồ yêu cầu từ1 tới $N$ qua dãy $A_{1}$, $A_{2}$, ..., $A_{M}$ gồm $M$ đảo $(2 \le M \le 10,000)$ trước khi kho báu hiện ra. Có thể thăm các đảo này và khác ngoài thứ tự hay nhiều lần, nhưng phải chứa $A_{i}$ theo bản đồ.

FJ tránh cướp biển và biết nguy hiểm $(0 \le danger \le 100,000)$ giữa mỗi cặp đảo. Tổng là tổng nguy hiểm của mọi đường đi qua.

Tìm tuyến ít nguy hiểm nhất đến kho báu thỏa bản đồ.

Dữ liệu vào

• Dòng1: hai số nguyên cách nhau dấu cách, $N$ và $M$.
• Các dòng $2,\ldots,M+1$: dòng $i+1$ mô tả đảo bắt buộc thứ $i_{th}$ bằng số nguyên $A_{i}$.
• Các dòng $M+2,\ldots,N+M+1$: dòng $i+M+1$ có $N$ số nguyên cách nhau dấu cách, nguy hiểm từ $i$ tới1, 2, ..., $N$. Số thứ $i$ luôn0.

Dữ liệu ra

• Dòng1: nguy hiểm tối thiểu lấy kho báu.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

7

Ghi chú

3 đảo và4 lần thăm:1, 2, lại1, cuối3. Đường(1,2), (2,3), (3,1) và ngược có5, 2, 1.

Tuyến1, 3, 2, 3, 1, 3 có7, chứa1, 2, 1, 3. Tránh1–2 nguy hiểm cao.

Tác giả bài toán: Jeffrey Wang, 2007