import static java.util.Arrays.fill;
import static java.util.Objects.requireNonNull;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.StringTokenizer;

public final class Main {
  public static final String IN_FILE = "dijkstra.in";
  public static final String OUT_FILE = "dijkstra.out";
  public static final int INFINITY = 0x3f3f3f3f;

  public static final class FastScanner implements AutoCloseable {
    private final BufferedReader reader;
    private StringTokenizer tokenizer;

    public FastScanner(final String fileName) throws IOException {
      reader = new BufferedReader(
          new InputStreamReader(new FileInputStream(fileName)));
    }

    private String next() throws IOException {
      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
        final String line = requireNonNull(reader.readLine());
        tokenizer = new StringTokenizer(line);
      }
      return tokenizer.nextToken();
    }

    public int nextInt() throws IOException {
      return Integer.parseInt(next());
    }

    @Override
    public void close() throws IOException {
      reader.close();
    }
  }

  public static final class Edge {
    public final int v;
    public final int c;

    public Edge(final int v, final int c) {
      this.v = v;
      this.c = c;
    }
  }

  private static final class HeapNode implements Comparable<HeapNode> {
    final int vertex;
    final int cost;

    HeapNode(final int vertex, final int cost) {
      this.vertex = vertex;
      this.cost = cost;
    }

    @Override
    public int compareTo(final HeapNode other) {
      return Integer.compare(cost, other.cost);
    }
  }

  public static int[] dijkstra(final List<List<Edge>> graph, final int source) {
    int[] distances = new int[graph.size()];
    fill(distances, INFINITY);
    final PriorityQueue<HeapNode> q = new PriorityQueue<>();
    q.add(new HeapNode(source, 0));
    while (!q.isEmpty()) {
      final HeapNode top = q.poll();
      final int u = top.vertex;
      if (distances[u] != INFINITY) {
        continue;
      }
      distances[u] = top.cost;
      for (final Edge e : graph.get(u)) {
        if (distances[e.v] == INFINITY) {
          q.add(new HeapNode(e.v, distances[u] + e.c));
        }
      }
    }
    return distances;
  }

  public static List<List<Edge>> readGraph(final FastScanner scanner)
      throws IOException {
    final int size = scanner.nextInt();
    final int edges = scanner.nextInt();
    final List<List<Edge>> graph = new ArrayList<>(size);
    for (int u = 0; u < size; u++) {
      graph.add(new ArrayList<>());
    }
    for (int i = 1; i <= edges; i++) {
      final int u = scanner.nextInt() - 1;
      final int v = scanner.nextInt() - 1;
      final int c = scanner.nextInt();
      final Edge e = new Edge(v, c);
      graph.get(u).add(e);
    }
    return graph;
  }

  public static void main(final String[] args) throws IOException {
    try (final FastScanner scanner = new FastScanner(IN_FILE);
        final PrintWriter writer = new PrintWriter(OUT_FILE)) {
      final List<List<Edge>> graph = readGraph(scanner);
      final int[] distances = dijkstra(graph, 0);
      for (int u = 1; u < graph.size(); u++) {
        writer.print(distances[u] == INFINITY ? 0 : distances[u]);
        writer.print(u + 1 < graph.size() ? ' ' : '\n');
      }
    }
  }
}