import java.io.FileInputStream;
import java.io.FileWriter;
import java.util.*;

/**
 * Created by Ada on 7/25/2016.
 */
public class Main {

    public static void main(String[] argv) {
        Integer n, m;
        HashMap<Integer, HashMap<Integer, Integer>> graph = new HashMap<Integer, HashMap<Integer, Integer>>();

        //read graph
        try {
            Integer x, y, cost;
            Scanner scanner = new Scanner(new FileInputStream("dijkstra.in"));
            n = scanner.nextInt();
            m = scanner.nextInt();

            for (int i = 1; i <= n; i++) {
                graph.put(i, new HashMap<Integer, Integer>());
            }

            for (int j = 1; j <= m; j++) {
                x = scanner.nextInt();
                y = scanner.nextInt();
                cost = scanner.nextInt();
                graph.get(x).put(y, cost);
            }
            scanner.close();
        } catch (Exception exception) {
            exception.printStackTrace();
            return;
        }

        //initialize arrays
        Integer distances[] = new Integer[n + 1];
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[1] = 0;
        Integer predecessor[] = new Integer[n + 1];
        Arrays.fill(predecessor, null);
        Boolean[] inQueue = new Boolean[n + 1];
        Arrays.fill(inQueue, false);

        //bellman ford with queue
        LinkedList<Integer> queue = new LinkedList<Integer>();
        queue.add(1);
        while(!queue.isEmpty()) {
            Integer current = queue.getFirst();
            queue.removeFirst();
            inQueue[current] = false;
            for (Map.Entry<Integer, Integer> neighbourEntry : graph.get(current).entrySet()) {
                Integer neighbour = neighbourEntry.getKey();
                Integer cost = neighbourEntry.getValue();
                if (distances[neighbour] > distances[current] + cost) {
                    distances[neighbour] = distances[current] + cost;
                    predecessor[neighbour] = current;
                    if (!inQueue[neighbour]) {
                        queue.add(neighbour);
                        inQueue[neighbour] = true;
                    }
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            for (Map.Entry<Integer, Integer> neighbour : graph.get(i).entrySet()) {
                if (distances[neighbour.getKey()] > distances[i] + neighbour.getValue()) {
                    distances[neighbour.getKey()] = distances[i] + neighbour.getValue();
                    predecessor[neighbour.getKey()] = i;
                }
            }
        }

        //write output file
        try {
            FileWriter fileWriter = new FileWriter("dijkstra.out");
            for (int i = 2; i <= n; i++) {
                fileWriter.write((distances[i] < Integer.MAX_VALUE ? distances[i] : 0) + " ");
            }
            fileWriter.write("\n");
            fileWriter.close();
        } catch (Exception exception) {
            exception.printStackTrace();
        }
    }
}