package com.amimun;

import java.io.*;
import java.nio.file.Paths;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

/*
5 6
1 2 1
1 4 2
4 3 4
2 3 2
4 5 3
3 5 6
 */

class Node {
    private int order, distance;

    public Node(int _order, int _distance) {
        order = _order;
        distance = _distance;
    }

    public void setDistance(int newDist) {
        distance = newDist;
    }

    public int getDistance() {
        return distance;
    }

    public int getOrder() {
        return order;
    }

    @Override
    public boolean equals(Object o) {
        Node node = (Node) o;
        return this.getOrder() == node.getOrder();
    }
}

class DistanceComparator implements Comparator<Node> {
    @Override
    public int compare(Node a, Node b) {
        return a.getDistance() > b.getDistance() ? 1 : -1;
    }
}

public class Main {

    public static void main(String[] args) throws IOException {
        int m, n, i, j;
        int[][] a;

        BufferedReader br = null;
        BufferedWriter bw = null;
        try {
            br = new BufferedReader(new FileReader("dijkstra.in"));
            bw = new BufferedWriter(new FileWriter("dijkstra.out"));
            Scanner scanner = new Scanner(br);
            n = scanner.nextInt();
            m = scanner.nextInt();
            int[] dist = new int[n + 1];
            int[] prev = new int[n + 1];
            dist[1] = 0;
            PriorityQueue<Node> priorityQueue = new PriorityQueue<>(new DistanceComparator());
            Node[] nodeArray = new Node[n + 1];

            nodeArray[1] = new Node(1, dist[1]);
            priorityQueue.add(nodeArray[1]);

            for (int k = 2; k <= n; k++) {
                dist[k] = Integer.MAX_VALUE;
                nodeArray[k] = new Node(k, dist[k]);
                priorityQueue.add(nodeArray[k]);
            }

            a = new int[n + 1][n + 1];

            for (int k = 0; k < m; k++) {
                i = scanner.nextInt();
                j = scanner.nextInt();
                a[i][j] = scanner.nextInt();
            }


            Node node;
            int tmp;

            while (!priorityQueue.isEmpty()) {
                node = priorityQueue.poll();
                int id = node.getOrder();
                for (i = 1; i <= n; i++) {
                    if(a[id][i] != 0 && priorityQueue.contains(nodeArray[i])) {
                        tmp = dist[id] + a[id][i];
                        if (tmp < dist[i]) {
                            dist[i] = tmp;
                            prev[i] = id;
                            priorityQueue.remove(nodeArray[i]);
                            nodeArray[i].setDistance(dist[i]);
                            priorityQueue.add(nodeArray[i]);
                        }
                    }
                }
            }

            for (i = 2; i <= n; i++) {
                bw.write(nodeArray[i].getDistance() + ((i == n) ? "" : " "));
            }
            bw.flush();

        } finally {
            if (br != null) {
                br.close();
            }

            if (bw != null) {
                bw.close();
            }
        }
    }
}