Problem Description

PepperLa is good at dealing with string problems, so he's going to offer string algorithm courses.

PepperLa has set up $N$ class rooms, there's one road between every two class rooms, and each road is equal in length.

PepperLa is afraid of the dark, so he only walks on roads with the light on. At the beginning, there is no light on. PepperLa has to pay one dollar for lighting the light of a road. However, PepperLa is dreaming of buying himself a switch, so he would like to pay the least.

The courses are scheduled so tightly that PepperLa can't afford to waste his time. So the distance between two class room should not be too far away. Specifically, you need to light the fewest roads so that the shortest path between class room $i$ and class room $j$ should eaqual to $dis[i][j]$.

Please tell PeoperLa how much is the minimum he has to pay.

Input

There are multiple test cases in this problem.

For every test case, The first line has 1 interger, $N(1 \leq N \leq 10^3)$

The next $N$ lines each line contains $N$ interger, the interger in $i$'th row, $j$'th column is $dis[i][j](1 \leq dis[i][j] \leq 10^6)$

The input guarantees that the data given is legal and there's always a solution

$dis[i][j]=dis[j][i],dis[i][i]=0, \sum{N}\leq 5 \times 10^3$

Output

For each test case, output a single line contains one integer,representing for the minimal money PepperLa has to pay.

3
0 1 2
1 0 1
2 1 0

2

Hint

Light the light of road (1,2),(2,3)