Contest3_corona_success

import java.util.*;

public class solution {
 public static int[][] graph ;
    public static int[] parent;
    public static int[] distance ;
    public static boolean[] check ;

    public static void main(String[] args) {
        // TODO code application logic here
        Scanner sc = new Scanner (System.in);
            int a = sc.nextInt();
            int b = sc.nextInt();
             graph = new int [a] [a];
             parent =new int [a];
             distance = new int [a];
             check = new boolean[a];
            for(int i = 0 ; i <graph.length ;i++){
                for (int j = 0 ; j <graph.length;j++){
                    graph[i][j]=-1;
                }
            }
             for(int i = 0 ; i < b ; i++){
                 int u = sc.nextInt();
                 int v = sc.nextInt();
                 graph[u][v] = sc.nextInt();
             }



    dij(graph,0);

        for(int i = 1 ; i < distance.length ; i++){
            System.out.println(distance[i]);
        }
    }


    public static void dij(int[][] graph, int s){
        for (int i = 0 ; i < graph.length ; i++){
            distance[i] =100000000;
            parent[i] = -1;
            check[i] = false;
        }

        distance[s] = 0;



        for(int i = 0 ; i < graph.length ; i++){
            int minKey = min(distance , check);
            check[minKey] = true;
            for(int j = 0 ; j < graph.length ; j++){
                 if (!check[j] && graph[minKey][j]!=-1 &&  distance[minKey]+graph[minKey][j] < distance[j]) {
                    parent[j] = minKey;
                    distance[j] = distance[minKey] + graph[minKey][j];
                }
            }
        }

    }

    public static int min (int[] key , boolean[] check){
        int min = 100000000 , minIndex = -1 ;
        for(int i = 0 ; i <key.length ; i++){
            if(check[i] == false && key[i] < min){
                min = key[i];
                minIndex = i;
            }
        }
        return minIndex;
    }

}