import java.io.*;
import java.util.*;

public class Main {
	private static final String INPUT_FILE_PATH = "dijkstra.in";
	private static final String OUTPUT_FILE_PATH = "dijkstra.out";

	public static void main(String[] args) throws IOException {
		Scanner in = new Scanner(new FileReader(INPUT_FILE_PATH));
		PrintWriter out = new PrintWriter(OUTPUT_FILE_PATH);
		int n = in.nextInt();
		int m = in.nextInt();
		DirectedGraph mGraph = new DirectedGraph(n);
		while (m-- > 0) {
			int source = in.nextInt();
			int dest = in.nextInt();
			int cost = in.nextInt();
			mGraph.insertEdge(source, dest, cost);
		}
		Long[] distances = mGraph.getShortestPaths(1);
		for (int i = 2; i <= n; ++i) {
			out.print(((Long.compare(distances[i], Long.MAX_VALUE) != 0) ? distances[i] : 0L) + " ");
		}
		out.flush();
		in.close();
		out.close();
	}

	static class DirectedGraph {

		static class Edge {
			int dest;
			long cost;

			public Edge(int dest, int cost) {
				this.dest = dest;
				this.cost = (long) cost;
			}
		}

		List<List<Edge>> neighbors;

		public DirectedGraph(int vertices) {
			this.neighbors = new ArrayList<>();
			for (int i = 0; i < vertices + 1; ++i) {
				this.neighbors.add(new ArrayList<Edge>());
			}
		}

		public void insertEdge(int source, int dest, int cost) {
			if (this.neighbors.size() > 0) {
				this.neighbors.get(source).add(new Edge(dest, cost));
			}
		}

		public Long[] getShortestPaths(int source) {
			Long[] dist = new Long[this.neighbors.size()];
			Arrays.fill(dist, Long.MAX_VALUE);
			dist[source] = 0L;
			MinHeap minHeap = new MinHeap();
			minHeap.add(new GraphTuple(1, dist[source]));
			while (!minHeap.isEmpty()) {
				int currVertex = minHeap.poll().vertex;
				List<Edge> currNeighbors = this.neighbors.get(currVertex);
				for (Edge edge : currNeighbors) {
					if (dist[edge.dest] > dist[currVertex] + edge.cost) {
						dist[edge.dest] = dist[currVertex] + edge.cost;
						minHeap.add(new GraphTuple(edge.dest, dist[edge.dest]));
					}
				}
			}
			return dist;
		}

		static class GraphTuple {
			int vertex;
			long cost;

			public GraphTuple(int vertex, long cost) {
				this.vertex = vertex;
				this.cost = cost;
			}
		}

		static class MinHeap extends PriorityQueue<GraphTuple> {

			public MinHeap() {
				super(new Comparator<GraphTuple>() {

					@Override
					public int compare(final GraphTuple e0, final GraphTuple e1) {
						return Long.compare(e0.cost, e1.cost);
					}
				});
			}

			public boolean add(GraphTuple tuple) {
				return super.add(tuple);
			}
		}

	}

}