import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.*;

public class Main {
    private static class Vertex {
        public final int id;
        public int dist = Integer.MAX_VALUE;
        // Map<VertexID, Distance>
        public final Map<Integer, Integer> neighbours = new HashMap<>();

        public Vertex(int id) {
            this.id = id;
        }
    }

    public static void main(String[] args) throws IOException {
        FileReader fileReader = new FileReader("dijkstra.in");
        BufferedReader bufferedReader = new BufferedReader(fileReader);

        Scanner scanner = new Scanner(bufferedReader);

        int nodes = scanner.nextInt();
        int noEdges = scanner.nextInt();

        ArrayList<Vertex> graph = new ArrayList<>(nodes);

        for (int i = 0; i < nodes + 1; i++) {
            graph.add(new Vertex(i));
        }

        int maxDist = 0;
        for (int i = 0; i < noEdges; i++) {
            int v1 = scanner.nextInt();
            int v2 = scanner.nextInt();
            int dist = scanner.nextInt();

            graph.get(v1).neighbours.put(v2, dist);
            if (dist > maxDist) {
                maxDist = dist;
            }
        }
        bufferedReader.close();

        int[] visited = new int[graph.size()];
        int[] distances = new int[graph.size()];
        int edgeDist;

        LinkedList<Integer>[] buckets = new LinkedList[maxDist * nodes];

        for (int i = 0; i < maxDist * nodes; i++) {
            buckets[i] = new LinkedList<Integer>();
        }
        buckets[0].add(1);

        for (int currentDist = 0; currentDist < maxDist * nodes; currentDist++) {
            LinkedList<Integer> bucket = buckets[currentDist];
            while (!bucket.isEmpty()) {
                Integer vertex = bucket.removeFirst();

                if (visited[vertex] == 1) {
                    continue;
                }
                visited[vertex] = 1;
                distances[vertex] = currentDist;

                for (Map.Entry<Integer, Integer> entry : graph.get(vertex).neighbours.entrySet()) {
                    int vIndex = entry.getKey();
                    Vertex v = graph.get(vIndex);
                    edgeDist = entry.getValue();

                    int alternateDist = currentDist + edgeDist;
                    if (alternateDist < v.dist && visited[vIndex] == 0) {
                        // shorter path to neighbour found
                        v.dist = alternateDist;
                        buckets[alternateDist].add(v.id);
                    }
                }
            }
        }

        StringBuilder output = new StringBuilder();

        for (int i = 2; i <= nodes; i++) {
            if (distances[i] == Integer.MAX_VALUE) {
                output.append("0");
            } else {
                output.append(distances[i]);
            }
            output.append(" ");
        }
        BufferedWriter writer = new BufferedWriter(new FileWriter("dijkstra.out"));
        writer.write(output.toString());
        writer.close();

    }
}