SW expert 사람 네트워크2 (자바)

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class algo_1263_김어진 {

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("input.txt"));

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine()," ");
		int T;
		T= Integer.parseInt(st.nextToken());
		
		int INF = 100000000;
		for(int test_case = 1; test_case <= T; test_case++)
		{
			
			st = new StringTokenizer(br.readLine()," ");
			int N =Integer.parseInt(st.nextToken());
			int[][] graph = new int[N][N];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					graph[i][j]=Integer.parseInt(st.nextToken());
				}
			}
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if(graph[i][j]==0 && i!=j) {
						graph[i][j]=INF;
					}
				}
			}
			
			for (int k = 0; k < N; k++) {
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						graph[i][j] = Math.min(graph[i][j], graph[i][k]+graph[k][j]);
					}
				}
			}
			
			int minValue = Integer.MAX_VALUE;
			for (int i = 0; i < N; i++) {
				int count = 0;
				for (int j = 0; j < N; j++) {
					if(graph[i][j]!=INF) {
						count+= graph[i][j];
					}
				}
				if(minValue>count) {
					minValue=count;
			
				}
			}
			System.out.printf("#%d %d\n",test_case,minValue);
		}

	}

}