/* BALAN CATALIN - DIJKSTRA CU HEAP */
#include<cstdio>
#define INF 0x3f3f3f3f
#define MAXN 50001
using namespace std;

struct muchieInGraf
{
	int node, cost;
	muchieInGraf *next;
} *a[MAXN];
char buf[32], *p;

int k, hp[MAXN], d[MAXN], poz[MAXN], N, M;

void addnode(int where, int what, int cost)
{
	muchieInGraf *q = new muchieInGraf;
	q->node = what;
	q->cost = cost;
	q->next = a[where];
	a[where] = q;
}

inline void sch(int x, int y)
{
	int t = hp[x];
	hp[x] = hp[y];
	hp[y] = t;
}


int get()
{
	int t = 0;
	for (;*p <= '9' && *p >= '0'; ++p)
	{
		t = t*10 + *p - '0';
	}
	for (;*p == ' '; ++p);
	return t;

}

void upheap(int ce)
{
	int parent;
	while (ce > 1)
	{
		parent = ce >> 1;
		if ( d[ hp[parent] ] > d[ hp[ce]] )
		{
			poz[hp[parent]] = ce;
			poz[hp[ce]] = parent;
			sch(parent, ce);
			ce = parent;
		}
		else ce = 1;
	}
}

void downheap(int ce)
{
	int kid;
	while ( ce <= k)
	{
		if ( ce<<1 > k)return;
		kid = ce<<1;
		if (kid + 1 <= k && d[ hp[kid+1] ] < d[ hp[kid] ])++kid;

		if ( hp[kid] < hp[ce])
		{
			poz[hp[kid]] = ce;
			poz[hp[ce]] = kid;
			sch(kid, ce);
			ce = kid;
		}
		else ce = k+1;
	}
}


void dijkstra()
{
	int minim, i;
	for (i = 2; i <= N; ++i)
		d[i] = INF, poz[i] = -1;
		poz[1] = 1;

		hp[++k] = 1;
		while (k)
		{
			minim = hp[1];
			sch(1,k);
			poz[ hp[1] ] = 1;
			--k;
			downheap(1);

		muchieInGraf *q = a[minim];
			while (q)
			{
				if (d[q->node] > d[minim] + q->cost)
				{
					d[q->node] = d[minim] + q->cost;
					if ( poz[q->node] != -1 )
					{
						upheap(poz[q->node]);
					}
					else
					{
						hp[++k] = q->node;
						poz[ q->node ] = k;
						upheap (k);
					}
				}

				q = q->next;
			}
		}
}

int main()
{
	FILE *f = fopen( "dijkstra.in", "r" );
	int i,x,y,c;
	fscanf(f,"%d %d\n", &N, &M);
	for (i = 1; i <= M; ++i )
	{
		fgets(buf,sizeof(buf),f);p = buf;
		x = get();
		y = get();
		c = get();
		addnode(x,y,c);
	}
	fclose(f);
	dijkstra();
	FILE *g = fopen( "dijkstra.out", "w" );
	for ( i = 2; i <= N; ++i)
		fprintf(f,"%d ",(d[i] == INF)? 0 : d[i]);
	fprintf(g,"\n");
	fclose(g);


return 0;
}