//dijkstra heap cu clase de obiecte

#include <stdio.h>
#include <values.h>
#define Nmax 50001

class Graf
{
	private : struct graf { int nod, cost; graf * next ; } *g[Nmax];
	private : int h[Nmax], poz[Nmax], d[Nmax], nrH;
	private : void swap(int x, int y) { poz[h[x]] = y; poz[h[y]] = x; int temp = h[x]; h[x] = h[y]; h[y] = temp; }

	public : void add(int x, int y, int cst)
	{
		graf * q = new graf;
		q->nod = y;
		q->cost = cst;
		q->next = g[x];
		g[x] = q;
	}

	private : void upheap(int loc)
	{
		if (loc == 1) return;
		int tata = loc >> 1;
		if (d[h[loc]] < d[h[tata]]) { swap(tata,loc); upheap(tata); }
	}

	private : void downheap(int loc)
	{
		int fiu;
		if (loc << 1 <= nrH)
		{
			fiu = loc << 1;
			if (fiu + 1 <= nrH && d[h[fiu+1]] < d[h[fiu]]) fiu++;
		}
		else return;
		if (d[h[fiu]] < d[h[loc]]) { swap(fiu,loc); downheap(fiu); }
	}

	private : void dijkstra(int n)
	{
		int x;
		nrH = 0;
		d[1] = 0;
		h[1] = 1;
		poz[++nrH] = nrH;
		while (nrH)
		{
			x=h[1];
			swap(1,nrH--);
			downheap(1);
			for (graf * p = g[x]; p; p = p -> next)
				if (d[p->nod] > d[x] + p -> cost)
				{
					d[p->nod] = d[x] + p -> cost;
					if (poz[p->nod]) upheap(poz[p->nod]);
					else
					{
						h[++nrH] = p->nod;
						poz[h[nrH]] = nrH;
						upheap(nrH);
					}
				}
		}
	}

	public : void afis(int n)
	{
		dijkstra(n);
		for (int i = 2; i<=n; i++) printf("%d ", d[i]==MAXINT?0:d[i]);
	}

	Graf(int n)
	{
		for (int i=1; i<=n; i++) { d[i] = MAXINT; poz[i] = 0; g[i] = NULL; }
	}

};

int n, m, x, y, z;


int main()
{
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	scanf("%d %d\n", &n, &m);
	Graf gr(n);
	for (; m; m--)
	{
		scanf("%d %d %d\n", &x, &y, &z);
		gr.add(x,y,z);
	}
	gr.afis(n);
	return 0;
}