Problem Description

Penguin-kun, the club president of Paken, wants to increase the number of club rooms.

The school where Penguin-kun is has $ N $ rooms, numbered from room $ 1 $ to room $ N $.

There are also $ M $ corridors, where the $ i $-th corridor connects room $ U_i $ and room $ V_i $ bidirectionally. Using these corridors, it is possible to move from any room to any other room.

Currently, only room $ 1 $ is a Paken club room. Penguin-kun starts today as day $ 1 $ and performs the following operation once a day for $ N-1 $ days to make all rooms Paken club rooms.

• Select one room that is directly connected by a corridor to any of the current Paken club rooms and is not currently a Paken club room, and make it a new Paken club room.

When room $ j $ is made a new Paken club room on day $ i $, Penguin-kun's happiness increases by $ A_{i,j} $. Initially, Penguin-kun's happiness is $ 0 $.

Find and output the maximum possible value of Penguin-kun's happiness after the operations on day $ N-1 $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ U_1 $ $ V_1 $ $\vdots$ $ U_M $ $ V_M $ $ A_{1,1} $ $ A_{1,2} $ $\cdots$ $ A_{1,N} $ $\vdots$ $ A_{N-1,1} $ $ A_{N-1,2} $ $\cdots$ $ A_{N-1,N} $

Output Format

Output the answer in one line.

Sample Input and Output

Sample Input #1

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

Sample Output #1

7

Sample Input #2

4 5
1 3
2 3
3 4
2 4
1 4
0 1 2 3
0 31 41 59
0 1 6 82

Sample Output #2

115

Notes/Hints

Constraints

• $2 \leq N \leq 15$
• $1 \leq M \leq \frac{N(N-1)}{2}$
• $1 \leq U_i < V_i \leq N$
• $(U_i, V_i) \neq (U_j, V_j) (i \neq j)$
• $1 \leq A_{i,j} \leq 10^5 (2 \leq j \leq N), A_{i,j} = 0 (j = 1)$
• It is possible to move from any room to any other room via zero or more corridors.
• All inputs are integers.

Sample Explanation 1

If room $ 2 $ is made a club room on day $ 1 $ and room $ 3 $ on day $ 2 $, the happiness is $ A_{1,2} + A_{2,3} = 5 $. If room $ 3 $ is made a club room on day $ 1 $ and room $ 2 $ on day $ 2 $, the happiness is $ A_{1,3} + A_{2,2} = 7 $. Therefore, output $ 7 $.

Sample Explanation 2

Original idea: primenumber_zz

见题面 Input 部分

见题面 Output 部分