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 PriorityQueue<Integer> Q;

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

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

	public static void Dijkstra(GraphD g, int sursa, int destinatie) {
		selectat[sursa] = true;
		List<Pair<Integer, Integer>> vecini = g.adiacenta.get(sursa);
		for (int nod = 1; nod <= g.nodes; nod++) {
			int pos = -1;
			for (int j = 0; j < vecini.size() && pos < 0; j++) {
				if (vecini.get(j).first() == nod)
					pos = j;
			}
			if (pos >= 0) {
				d[nod] = vecini.get(pos).second();
				Q.add(new Integer(nod));
			} else {
				d[nod] = Integer.MAX_VALUE;
			}
		}

		while (!Q.isEmpty()) {
			int u = Q.poll();
			selectat[u] = true;

			for (int i = 0; i < g.adiacenta.get(new Integer(u)).size(); i++) {
				int nod = g.adiacenta.get(new Integer(u)).get(i).first();
				if (selectat[nod] == false && d[nod] > d[u] + g.adiacenta.get(new Integer(u)).get(i).second()) {
					d[nod] = d[u] + g.adiacenta.get(new Integer(u)).get(i).second();
				}
			}
		}
	}

	public static void main(String[] args) throws IOException {
		GraphD g = new GraphD();
		g.readData("dijkstra.in");
		selectat = new boolean[g.nodes + 1];
		d = new int[g.nodes + 1];
		Q = new PriorityQueue<>(g.nodes, new NodeComparator());

		BufferedWriter write = new BufferedWriter(new FileWriter(new File("dijkstra.out")));
		for (int i = 2; i <= g.nodes; i++) {
			Dijkstra(g, 1, i);
			write.write(d[i] + "");
			if(i!=g.nodes) write.write(" ");
		}
		write.close();
	}
}