import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.TreeSet;

public class Main {

  static int n;
  static int m;

  static List<Short>[] g;
  static List<Short>[] c;
  
  static int[] dist;

  public static void main(String[] args) throws FileNotFoundException, IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(new FileInputStream("dijkstra.in")));
    BufferedWriter out = new BufferedWriter(new OutputStreamWriter(new FileOutputStream("dijkstra.out")));

    String[] parts = in.readLine().split(" ");
    n = Integer.parseInt(parts[0]);
    m = Integer.parseInt(parts[1]);

    g = new List[n];
    c = new List[n];
    dist = new int[n];
    for (int i = 0; i < n; i++) {
      g[i] = new ArrayList<>();
      c[i] = new ArrayList<>();      
      dist[i] = Integer.MAX_VALUE;
    }

    dist[0] = 0;
    for (int i = 0; i < m; i++) {
      parts = in.readLine().split(" ");
      short from = (short) (Short.parseShort(parts[0]) - 1);
      short to = (short) (Short.parseShort(parts[1]) - 1);
      short cost = Short.parseShort(parts[2]);
      g[from].add(to);
      c[from].add(cost);
//      out.println(from + ", " + to + ", " + cost);
    }

    PriorityQueue<Integer> pq = new PriorityQueue<>(n, new Comparator<Integer>() {
      @Override
      public int compare(Integer o1, Integer o2) {
        return dist[o1] - dist[o2];
      }
    });
    TreeSet<Long> ts = new TreeSet<>();
    ts.add(0L);
    while (!ts.isEmpty()) {
      int node = ts.pollFirst().intValue();
      for (int i = 0; i < g[node].size(); i++) {
        int newDist = ((int) dist[node]) + c[node].get(i);
        if (newDist < dist[g[node].get(i)]) {
          dist[g[node].get(i)] = newDist;
          ts.add(((1L * newDist) << 32) + g[node].get(i));
        }
      }
    }

    for (int i = 1; i < n; i++) {
      if (dist[i] < Integer.MAX_VALUE) {
        out.write(dist[i] + " ");
      } else {
        out.write("0 ");
      }
    }
    out.close();
  }
}