import java.io.BufferedWriter;
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.PriorityQueue;
import java.util.Scanner;

class Graph<T> {
	T[] nodes;
	private PriorityQueue<Edge> pq = new PriorityQueue<Edge>(10,
			new Comparator<Edge>() {
				@Override
				public int compare(Edge o1, Edge o2) {

					return o1.cost > o2.cost ? 1 : -1;
				}
			});
	HashMap<T, List<Edge>> graph = new HashMap<T, List<Edge>>();

	class Edge {
		final T to;
		final int cost;

		Edge(T to, int cost) {
			this.to = to;
			this.cost = cost;
		}
	}

	void print() {
		for (T key : graph.keySet()) {
			System.out.println("from " + key + " ");
			List<Edge> lst = graph.get(key);
			for (Edge e : lst) {
				System.out.println(e.to + " " + e.cost);
			}
		}
	}

	HashMap<T, Integer> getMinimumDistaince(T start) {
		pq.add(new Edge(start, 0));
		HashMap<T, Integer> distance = new HashMap<T, Integer>();
		for (T node : nodes) {
			distance.put(node, 600000);
		}
		distance.put(start, 0);
		while (!pq.isEmpty()) {
			Edge edge = pq.remove();
			if (graph.get(edge.to) == null) {
				continue;
			}
			for (Edge neighbour : graph.get(edge.to)) {
				int cost = edge.cost + neighbour.cost;
				if (cost < distance.get(neighbour.to)) {
					pq.add(new Edge(neighbour.to, cost));
					distance.put(neighbour.to, cost);
				}
			}
		}
		return distance;
	}
}

public class Main {
	int n, m, s;
	final String input;
	final String output;
	Graph<Integer> graph = new Graph<Integer>();

	Main(String input, String output) {
		this.input = input;
		this.output = output;
	}

	public static void main(String[] args) throws IOException {
		Main main = new Main("dijkstra.in", "dijkstra.out");
		main.read();
		HashMap<Integer, Integer> distance = main.graph.getMinimumDistaince(1);
		main.writer(distance);
	}

	void read() throws IOException {
		Scanner scanner = new Scanner(new FileReader(input));
		n = scanner.nextInt();
		m = scanner.nextInt();
		for (int i = 0; i < m; i++) {
			int from = scanner.nextInt();
			int to = scanner.nextInt();
			int cost = scanner.nextInt();
			if (graph.graph.get(from) == null) {
				graph.graph.put(from, new ArrayList<Graph<Integer>.Edge>());
			}
			graph.graph.get(from).add(graph.new Edge(to, cost));
		}
		// graph.print();
		graph.nodes = new Integer[n];
		for (int i = 0; i < n; i++) {
			graph.nodes[i] = i + 1;
		}
	}

	void writer(HashMap<Integer, Integer> result) throws IOException {
		BufferedWriter writer = new BufferedWriter(new FileWriter(output));
		for (int i = 2; i <= n; i++) {
			if (result.get(i) == 600000) {
				writer.write(0 + " ");
			} else{
				writer.write(result.get(i) + " ");
			}		
		}
		writer.flush();
	}
}