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

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

    private static class AdjList {
        private LinkedList<Neighbour> list;

        public AdjList() {
            this.list = new LinkedList<Neighbour>();
        }

        public void add(Neighbour neighbour) {
            this.list.add(neighbour);
        }

        public LinkedList<Neighbour> getElements() {
            return this.list;
        }
    }

    private static class Neighbour {
        private int id;
        private int cost;

        public Neighbour(int id, int cost) {
            this.id = id;
            this.cost = cost;
        }

        public int getId() {
            return id;
        }

        public int getCost() {
            return cost;
        }
    }

    public static void main(String[] argv) {
        Integer n, m;
        AdjList[] lists;
        //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();
            lists = new AdjList[n + 1];
            for (int i = 1; i <= n; i++) {
                lists[i] = new AdjList();
                //graph.put(i, new HashMap<Integer, Integer>());
            }

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

        //initialize arrays
        Long distances[] = new Long[n + 1];
        Arrays.fill(distances, (long)Integer.MAX_VALUE);
        distances[1] = 0L;
        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();
            for (Neighbour neighbourEntry : lists[current].getElements()) {
                Integer neighbour = neighbourEntry.getId();
                Integer cost = neighbourEntry.getCost();
                if (distances[neighbour] > distances[current] + cost) {
                    distances[neighbour] = distances[current] + cost;
                    predecessor[neighbour] = current;
                    if (!inQueue[neighbour]) {
                        queue.add(neighbour);
                        inQueue[neighbour] = true;
                    }
                }
            }
        }

        //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();
        }
    }
}