Tại một tỉnh X có ~N~ trường học, đánh số từ 1 đến ~N~. Mỗi trường học được trang cấp một máy tính. Hai trường trao đổi thông tin được với nhau nếu có ít nhất một kênh truyền tín hiệu để kết nối hai máy tính của hai trường học (có thể kết nối thông qua một số trường khác, đường truyền đảm bảo hai chiều). Để kết nối một kênh truyền tín hiệu trực tiếp giữa hai máy tính của trường ~i~ và trường ~j~ thì phải mất một khoản chi phí là ~A_{i,j}~. Hiện nay, tỉnh X đã kết nối được ~M~ kênh truyền tín hiệu trực tiếp giữa ~M~ cặp máy tính của các trường học trong tỉnh.

Yêu cầu: Hãy kiểm tra xem với ~M~ kênh truyền tín hiệu đã có thì hai trường học bất kỳ có thể trao đổi thông tin được với nhau hay không? Nếu không, hãy kết nối thêm một số kênh truyền tín hiệu trực tiếp giữa các máy tính sao cho đảm bảo được việc trao đổi thông tin giữa tất cả các trường học và tổng chi phí dùng để kết nối thêm là nhỏ nhất.

Dữ liệu vào:

Cho trong file NETWORK.INP có cấu trúc như sau:

• Dòng 1: Ghi 2 số nguyên dương ~N, M~ (~2 \leq N \leq 100; 0 < M \leq 250~).
• $M$ dòng tiếp theo: Mỗi dòng ghi 2 số nguyên dương là số hiệu của hai trường có kênh truyền tín hiệu trực tiếp.
• Dòng thứ ~i~ trong ~N~ dòng tiếp theo: Ghi ~N~ số nguyên dương ~A_{i1}, A_{i2}, \dots, A_{iN}~ lần lượt là chi phí để xây dựng kênh truyền tín hiệu trực tiếp từ máy tính của trường ~i~ đến các máy tính của các trường từ 1 đến ~N~ (~0 < A_{i,j} \leq 32000~ với ~i \neq j~; ~A_{i,j} = 0~ với ~i = j~).
• Các số trên một dòng được ghi cách nhau ít nhất một dấu cách.

Dữ liệu ra:

Ghi ra file văn bản NETWORK.OUT theo cấu trúc như sau:

• Dòng 1: Nếu không cần kết nối thêm kênh truyền tín hiệu trực tiếp thì ghi số 0. Ngược lại thì ghi số nguyên dương ~T~, là tổng chi phí dùng để nối thêm các các kênh truyền tín hiệu.

Ví dụ:

Input: NETWORK.INP

5 4
1 2
2 3
3 1
4 5
0    4    5    5    8
4    0    7    6    7
5    7    0    3    10
5    6    3    0    9
8    7    10   9    0

Output: NETWORK.OUT

3