Maintaining Roads

All submissions for this problem are available.
In a kingdom, there are N cities, numbered from 1 to N, with some pairs of them connected by bidirectional roads, the lengths of which are known. The cost of maintaining a road is 1 per unit length. The capital of the kingdom is city 1. Now the king wishes to maintain only some roads such that :
 He himself does not like treading roads not maintained. Thus, there should be a path from the capital to any other city using only maintained roads.
 People do not like walking long roads. Hence if there exists a road between X and Y of length L, he will not maintain the road if there exists another path in the kingdom between X and Y on which none of the roads are of length >= L. Maintaining such a road would be useless since people would never use it.
 The total cost of the maintained roads should be minimum.
Given a description of the kingdom, output the cost of maintaining roads satisfying the above conditions.
Input
The first line contains the number of test cases T(<=10). T test cases follow. For each test case, the first line contains N (<= 300), the number of cities. There follow N lines, each with N integers. The ith integer on the jth line is the length of the road between cities i and j (0 if there is no road). The ith integer on the jth line will be equal to the jth integer on the ith line. Also, the ith integer on the ith line will be a 0. No value will be greater than 1000000.
Output
Output T lines, 1 corresponding to each test case, containing the desired answer.
Example
Input: 1 2 0 1 1 0 Output: 1
Author:  technovanza10 
Tags  technovanza10 
Date Added:  24012010 
Time Limit:  0.697674 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH 3.5, PYPY, GO, NODEJS, rust, swift, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 