public class MyClass {
    public static void main(String args[]) {
       String[] citys = new String[10];

        citys[0] = "서울";  //0
        citys[1] = "천안";  //1
        citys[2] = "원주";  //2
        citys[3] = "강릉";  //3
        citys[4] = "논산";  //4
        citys[5] = "대전";  //5
        citys[6] = "대구";  //6
        citys[7] = "포항";  //7
        citys[8] = "광주";  //8
        citys[9] = "부산";  //9

        int length = citys.length;

        Graph g = new Graph(); // 노드 수 만큼 그래프 생성
        g.init(length);
        
        // 시작, 끝, 간선 가중치 입력
        g.input(0, 1, 12);  //서울0 천안1 12
        g.input(0, 2, 15);  //서울0 원주2 15
        g.input(1, 4, 4);   //천안1 논산4 4
        g.input(1, 5, 10);  //천안1 대전5 10
        g.input(2, 3, 21);  //원주2 강릉3 21
        g.input(2, 6, 7);   //원주2 대구6 7
        g.input(3, 7, 25);  //강릉3 포항7 25
        g.input(4, 8, 13);  //논산4 광주8 13
        g.input(4, 5, 3);   //논산4 대전5 3
        g.input(5, 6, 10);  //대전5 대구6 10
        g.input(6, 7, 19);  //대구6 포항7 19
        g.input(6, 9, 9);   //대구6 부산9 9
        g.input(7, 9, 5);   //포항7 부산9 5
        g.input(8, 9, 15);  //광주8 부산9 15
        
        // 시작노드 기준 다익스트라 알고리즘 실행
        String[] result = g.dijkstra(0);
        
        for(int i=0; i<result.length; i++) {
          System.out.println("result = " + result[i]);
        }
    }
    
    static class Graph{
    private int n;           // 노드들의 수
    private int maps[][];    // 노드들간의 가중치 저장할 변수
 
public Graph(){
}

public void init(int n) {
        this.n = n;
        maps = new int[n][n];
        
        // 인접행렬 모든 값 무한대로 초기화
        for(int i=0; i<n; ++i){
        	for(int j=0; j<n; ++j){
        	    
        		maps[i][j] = Integer.MAX_VALUE;
        
        	}
        }
}

    public void input(int i,int j,int w){
        
        maps[i][j] = w;
        maps[j][i] = w;
    }
 
    public String[] dijkstra(int v){
        int distance[] = new int[n];          // 최단 거리를 저장할 변수
        boolean[] check = new boolean[n];     // 해당 노드를 방문했는지 체크할 변수
         
        // distance값 초기화. 무한대를 int 자료형의 최대값으로 표현했다.
        for(int i=0; i<n; ++i){
            distance[i] = Integer.MAX_VALUE;
        }
         
        // 시작노드값 초기화.
        distance[v] = 0;
        check[v] = true;
      
        // 연결노드 distance갱신
        for(int i=0; i<n; ++i){
            if(!check[i] && maps[v][i] != Integer.MAX_VALUE){
                distance[i] = maps[v][i];
            }
        }
        
        
        String[] result = new String[n];
        
        for(int a=0; a<n-1; ++a){
            // 원래는 모든 노드가 true될때까지 인데
            // 노드가 n개 있을 때 다익스트라를 위해서 반복수는 n-1번이면 된다.
            // 원하지 않으면 각각의 노드가 모두 true인지 확인하는 식으로 구현해도 된다.
            int min = Integer.MAX_VALUE;
            int min_index = -1;
            
            // 노드 최소값 찾기
            for(int i=0; i<n; ++i){
                if(!check[i]){
                    if(distance[i] < min){
                        min = distance[i];
                        min_index = i;
                    }
                }
            }
            
            // 다른 노드를 거쳐서 가는 것이 더 비용이 적은지 확인한다.
            check[min_index] = true;
            for(int i=0; i<n; ++i){
                if(!check[i] && maps[min_index][i] != Integer.MAX_VALUE){
                    if(distance[min_index] + maps[min_index][i] < distance[i]){
                        distance[i] = distance[min_index] + maps[min_index][i];
                    }
                }
            }
            
            // 결과값 출력
            for(int i=0; i<n; ++i){
                
                String d = "";
                
            	if(distance[i] == 2147483647) {
            	    System.out.print("∞ ");
            	    d = "∞";
            	}
            	else {
            	    System.out.print(distance[i]+" ");
            	    d = distance[i]+" ";
            	}
            	
            	
            	    result[i] = d;
            
            }
            System.out.println("");
        }
        
        return result;
    }
    }
}