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;
        public final Map<Vertex, 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));
        }

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

            graph.get(v1).neighbours.put(graph.get(v2), dist);
        }
        bufferedReader.close();

        FibonacciHeap<Integer> heap = new FibonacciHeap<Integer>();

        heap.enqueue(1, 0);

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

        while (!heap.isEmpty()) {
            FibonacciHeap.Entry<Integer> entry = heap.dequeueMin();
            int u = entry.getValue();
            int uDist = ((Double) entry.getPriority()).intValue();

            if (visited[u] == 1) {
                continue;
            }
            visited[u] = 1;
            distances[u] = uDist;
            if (uDist == Integer.MAX_VALUE) {
                break;
                // we can ignore u (and any other remaining vertices) since they are unreachable
            }

            for (Map.Entry<Vertex, Integer> neighbourEntry : graph.get(u).neighbours.entrySet()) {
                Vertex v = neighbourEntry.getKey();
                dist = neighbourEntry.getValue();

                int alternateDist = uDist + dist;
                if (alternateDist < v.dist && visited[v.id] == 0) {
                    // shorter path to neighbour found
                    heap.enqueue(v.id, alternateDist);
                }
            }
        }

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