import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class PairComparator implements Comparator<Pair<Integer, Integer>> {

	@Override
	public int compare(Pair<Integer, Integer> o1, Pair<Integer, Integer> o2) {
		
		return o1.second()-o2.second();
	}


}


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;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + ((fst == null) ? 0 : fst.hashCode());
		result = prime * result + ((snd == null) ? 0 : snd.hashCode());
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Pair other = (Pair) obj;
		if (fst == null) {
			if (other.fst != null)
				return false;
		} else if (!fst.equals(other.fst))
			return false;
		if (snd == null) {
			if (other.snd != null)
				return false;
		} else if (!snd.equals(other.snd))
			return false;
		return true;
	}
	

}
class Dijkstra {

	public Integer[] shortestPath(Graph g, int sourceVertex) {
		ArrayList<Integer> S = new ArrayList<Integer>();
		int numNodes = g.numNodes;
		long cost = 0;
		Integer[] p = new Integer[numNodes + 1];
		Integer[] d = new Integer[numNodes + 1];
		List<List<Pair<Integer, Integer>>> edges = g.edges;

		Comparator<Pair<Integer, Integer>> comparator = new PairComparator();
		PriorityQueue<Pair<Integer, Integer>> queue = new PriorityQueue<Pair<Integer, Integer>>(10, comparator);

		Arrays.fill(d, Integer.MAX_VALUE);
		Arrays.fill(p, null);
		d[sourceVertex] = 0;

		queue.add(new Pair<>(sourceVertex, 0));
		for (int i = 1; i <= numNodes; i++) {
			if (i != sourceVertex)
				queue.add(new Pair<>(i, Integer.MAX_VALUE));
		}

		// iterate till heap is not empty
		while (!queue.isEmpty()) {
			// get the min value from heap node which has vertex and distance of
			// that vertex from source vertex.
			Pair<Integer, Integer> u = queue.poll();
			S.add(u.first());
			d[u.first()] = u.second();

			// iterate through all edges of current vertex
			for (Pair<Integer, Integer> edge : edges.get(u.first())) {
				
				if (!S.contains(edge.first()))
					if (d[edge.first()] > d[u.first()] + edge.second()) {
						queue.remove(new Pair<>(edge.first(), d[edge.first()]));
						d[edge.first()] = d[u.first()] + edge.second();
						p[edge.first()] = u.first();
						queue.add(new Pair<>(edge.first(), d[edge.first()]));
					}
				
				}
		}
		return d;
	}

}
class Graph {

	/**
	 * Total number of nodes that makes the graph
	 */
	public int numNodes;

	/**
	 * The graph uses list of adjacencies for each node. The first item of the
	 * pair represents the index of the adjacent, while the second item
	 * represents the cost of the edge
	 */
	public List<List<Pair<Integer, Integer>>> edges;

	public Graph() {
		edges = new ArrayList<>();
		edges.add(new ArrayList<>());
	}

	public void insertNode(int nodeIdx) {
		edges.add(new ArrayList<>());
	}

	/**
	 * Inserts a new edge into the graph starting at 'fromNodeIdx' and ending at
	 * 'toNodeIdx', having cost value of 'cost'
	 *
	 * @param fromNodeIdx
	 * @param toNodeIdx
	 * @param cost
	 */
	public void insertEdge(int fromNodeIdx, int toNodeIdx, int cost) {
		edges.get(fromNodeIdx).add(new Pair<>(toNodeIdx, cost));
	}

	public int getNodeCount() {
		return numNodes;
	}

	public List<Pair<Integer, Integer>> getEdges(int nodeIdx) {
		return edges.get(nodeIdx);
	}

	/**
	 * Function to read all the tests
	 *
	 * Input Format: N M Nodei Nodej Costij -- list of edges ... where N =
	 * Number of Nodes M = Number of Edges Costij = cost of edge from i to j, as
	 * well as from j to i
	 * 
	 * @param scanner
	 */
	public void readData(BufferedReader input) throws IOException {
		StringTokenizer tokenizer;
		String read = input.readLine();
		tokenizer = new StringTokenizer(read, " ");
		numNodes = Integer.parseInt(tokenizer.nextToken());
		int numEdges = Integer.parseInt(tokenizer.nextToken());

		for (int i = 0; i < numNodes; i++) {
			insertNode(i);
		}

		for (int edgeIdx = 1; edgeIdx <= numEdges; edgeIdx++) {

			read = input.readLine();
			tokenizer = new StringTokenizer(read, " ");

			int node1 = Integer.parseInt(tokenizer.nextToken());
			int node2 = Integer.parseInt(tokenizer.nextToken());
			int cost = Integer.parseInt(tokenizer.nextToken());

			insertEdge(node1, node2, cost);

		}
	}

	@Override
	public String toString() {

		StringBuilder sb = new StringBuilder("Print Graph:\n");

		for (int n = 0; n < numNodes; n++) {
			sb.append("OutEdges for " + n + " -> ");

			for (Pair<Integer, Integer> edge : edges.get(n)) {
				sb.append(edge.first());
				sb.append("( " + edge.second() + " ) | ");
			}

			sb.append("\n");
		}
		sb.append("\n");

		return sb.toString();
	}
}
public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader input = new BufferedReader(new FileReader("dijkstra.in"));//deschidem fisierul pentru citire
		BufferedWriter output = new BufferedWriter(new FileWriter("dijkstr.out"));//deschidem fisierul pentru scriere
		
		Graph g = new Graph();
		g.readData(input);
		Dijkstra dijkstra = new Dijkstra();
		Integer []d = dijkstra.shortestPath(g, 1);
		//output.write(dfs.doDFS()+"\n");
		for(int i = 2;i<d.length;i++){
			if(i==d.length-1)
				output.write(d[i].toString());
				else
				
				output.write(d[i]+" ");
		}
		input.close();
		output.close();
	}

}