import java.io.BufferedWriter;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;

class Dijkstra {
	public static void main (String[] args) throws IOException
	{
		Dijkstra dijkstra = new Dijkstra ();
		dijkstra.solve();
	}
	File in = new File ("dijkstra.in");
	FileWriter out;
	int N, M;
	int lst[], vf[], urm[], h[], v[], c[], poz[];
	boolean viz[];
	int nrh = 1, nr = 0;
	int ct = 20000 * 50000 + 1;
	void solve () throws IOException
	{
		out = new FileWriter ("dijkstra.out");
		Scanner scanner = new Scanner(in);
		N = scanner.nextInt();
		M = scanner.nextInt();
		init ();
		int i;
		int x, y, cost;
		for (i = 1; i <= M; i++)
		{
			x = scanner.nextInt(); y = scanner.nextInt(); cost = scanner.nextInt();
			adauga (x, y, cost);
		}
		h[1] = 1;
		nrh = N;
		while (nrh != 0)
		{
			x = h[1];
			schimba (1, nrh--);
			coboara (1);
			viz[x] = true;
			int p = lst[x];
			while (p != 0)
			{
				y = vf[p];
				cost = c[p];
				if (viz[y] == false && v[x] + cost <= v[y])
				{
					v[y] = v[x] + cost;
					urca (poz[y]);
				}
				p = urm[p];
			}
		}
		BufferedWriter writer = new BufferedWriter (out);
		for (i = 2; i <= N; i++)
		{
			if (v[i] != ct)
				writer.write(v[i] + " ");
			else
				writer.write("0 ");
		}
			//out.print(v[i] + " ");
		//writer.newLine();
		//writer.flush();
		writer.flush();
			
	}
	void adauga (int x, int y, int cost)
	{
		vf[++nr] = y;
		c[nr] = cost;
		urm[nr] = lst[x];
		lst[x] = nr;
	}
	
	void init ()
	{
		lst = new int[N + 5]; vf = new int[M + 5]; urm = new int [M + 5];
		viz = new boolean[N + 5]; h = new int[N + 5]; c = new int[M + 5];
		v = new int[N + 5]; poz = new int[N + 5];
		poz[1] = 1;
		for (int i = 2; i <= N; i++)
		{
			v[i] = ct;
			poz[i] = i;
			h[i] = i;
		}
	}
	void urca (int p)
	{
		while (p > 1 && v[h[p]] <= v[h[p >> 1]])
		{
			schimba (p, p >> 1);
			p >>= 1;
		}
	}
	void schimba (int p1, int p2)
	{
		int aux = h[p1];
		h[p1] = h[p2];
		h[p2] = aux;
		poz[h[p1]] = p1;
		poz[h[p2]] = p2;
	}
	void coboara (int p)
	{
		int fs = p << 1, fd = (p << 1) + 1, bun = p;
		if (fs <= nrh && v[h[fs]] <= v[h[bun]])
			bun = fs;
		if (fd <= nrh && v[h[fd]] <= v[h[bun]])
			bun = fd;
		if (bun != p)
		{
			schimba (bun, p);
			coboara (bun);
		}
	}
}