import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;

class Pair<A, B> {

	private A fst;

	private B snd;

	public Pair(A fst, B snd) {
		this.fst = fst;
		this.snd = snd;
	}

	public A first() {
		return fst;
	}

	public B second() {
		return snd;
	}
}

class GraphD {

	int nodes;
	public Map<Integer, List<Pair<Integer, Integer>>> adiacenta;
	public List<Pair<Pair<Integer, Integer>, Integer>> edge;

	public GraphD() {
		adiacenta = new HashMap<>();
		edge = new ArrayList<>();
	}

	public GraphD(int nodes, Map<Integer, List<Pair<Integer, Integer>>> edges) {
		this.nodes = nodes;
		this.adiacenta = edges;
	}

	public void readData(String filename) throws IOException {
		Scanner input = new Scanner(new FileReader(filename));
		nodes = input.nextInt();
		int M = input.nextInt();

		for (int i = 1; i <= nodes; i++)
			adiacenta.put(i, new ArrayList<Pair<Integer, Integer>>());

		int node1, node2, cost;
		for (int i = 0; i < M; i++) {
			node1 = input.nextInt();
			node2 = input.nextInt();
			cost = input.nextInt();
			adiacenta.get(node1).add(new Pair<Integer, Integer>(node2, cost));
		}
		input.close();
	}
}

public class Main {

	static boolean[] selectat;
	static int[] d;
	static int[] p;
	static PriorityQueue<Pair<Integer, Integer>> Q;

	private static class NodeComparator implements Comparator<Pair<Integer, Integer>> {
		/**
		 * Compares nodes using the current estimation of the distance from the
		 * source node.
		 */
		@Override
		public int compare(Pair<Integer, Integer> arg0, Pair<Integer, Integer> arg1) {
			int dist1 = arg0.second();
			int dist2 = arg1.second();

			return dist1 > dist2 ? 1 : -1;
		}
	}

	public static void Dijkstra(GraphD g, int sursa) throws IOException {
		for (int i = 2; i <= g.nodes; i++) {
			d[i] = Integer.MAX_VALUE;
			p[i] = -1;
			Q.add(new Pair<Integer, Integer>(i, d[i]));
		}

		d[sursa] = 0;
		Q.add(new Pair<Integer, Integer>(1, 0));

		while (!Q.isEmpty()) {
			Pair<Integer, Integer> pa = Q.poll();
			int u = pa.first();
			if (selectat[u])
				continue;
			selectat[u] = true;

			List<Pair<Integer, Integer>> vecini = g.adiacenta.get(u);
			for (int i = 0; i < vecini.size(); i++) {
				int v = vecini.get(i).first();
				int cost = vecini.get(i).second();
				if (selectat[v])
					continue;
				int alt = 0;
				if (d[u] != Integer.MAX_VALUE) {
					alt = d[u] + cost;
					if (cost < d[v]) {
						d[v] = alt;
						p[v] = u;
						Q.add(new Pair<Integer, Integer>(v, d[v]));
					}
				}
			}
		}
		BufferedWriter write = new BufferedWriter(new FileWriter(new File("dijkstra.out")));
		for (int i = 2; i <= g.nodes; i++)
			write.write(d[i] + " ");
		write.close();
	}

	public static void main(String[] args) throws IOException {
		GraphD g = new GraphD();
		g.readData("dijkstra.in");

		d = new int[g.nodes + 1];
		p = new int[g.nodes + 1];

		selectat = new boolean[g.nodes + 1];
		Q = new PriorityQueue<>(new NodeComparator());

		Dijkstra(g, 1);
	}
}