#include <stdio.h>
#include <string.h>

#define MAXN 50001
#define INF 0x3f3f3f3f

int *lv[MAXN], *cost[MAXN];
int N, M;
int H[MAXN], hsz;
int ind[MAXN];
int gr[MAXN];
int dist[MAXN];
int a, b, c;
char s[1<<7];

void get ()
{
    gets (s);

    int i, ten;    
    a=b=c=0;
    for (i = strlen(s) - 1, ten = 1; s[i] != ' '; --i, ten *= 10)
        c += (s[i] - '0') * ten;
    for (--i, ten = 1; s[i] != ' '; --i, ten *= 10)
        b += (s[i] - '0') * ten;
    for (--i, ten = 1; i >= 0; --i, ten *= 10)
        a += (s[i] - '0') * ten;
}

void read ()
{
	int i;

	scanf ("%d %d\n", &N, &M);
	for (i = 0; i < M; ++ i)
	{
        get ();
        //printf ("%d %d %d\n", a, b, c);
		++gr[a];
	}

	for (i = 1; i <= N; ++ i)
	{
		lv[i] = new int [gr[i] + 1];
		cost[i] = new int [gr[i] + 1];
		lv[i][0] = 0;
	}

	fseek (stdin, 0, SEEK_SET);

	scanf ("%d %d\n", &N, &M);
	for (i = 0; i < M; ++ i)
	{
        get ();
		lv[a][++lv[a][0]] = b;
		cost[a][lv[a][0]] = c;
	}
	
	/*for (i = 1; i <= N; ++ i)
	{
	   for (int j = 1; j <= lv[i][0]; ++ j)
	       printf ("%d ", lv[i][j]);
	    printf ("\n");
    }*/
}

void update (int x)
{
	int tata, fiu, val;
	val = H[x];
	fiu = x;
	tata = fiu / 2;

	while (tata > 0)
	{
		if (dist[val] > dist[H[tata]]) break;

		H[fiu] = H[tata];
		ind[H[fiu]] = fiu;

		fiu = tata;
		tata = fiu / 2;
	}

	H[fiu] = val;
	ind[H[fiu]] = fiu;
}

void combheap (int x)
{
	int tata, fiu, val;
	val = H[x];
	tata = x;
	fiu = 2*x;

	while (fiu <= hsz)
	{
		if (fiu < hsz)
			if (dist[H[fiu]] > dist[H[fiu+1]]) ++fiu;

		if (dist[val] < dist[H[fiu]]) break;

		H[tata] = H[fiu];
		ind[H[tata]] = tata;

		tata = fiu;
		fiu = 2*tata;
	}

	H[tata] = val;
	ind[H[tata]] = tata;
}

void dijkstra (int s)
{
	int i, j;
	memset (dist, INF, sizeof(dist));
	dist[s] = 0;

	hsz = N;
	for (i = 1; i <= N; ++ i)
	{
		H[i] = i;
		ind[i] = i;
	}

	for (i = hsz / 2; i > 0; -- i)
		combheap (i);

	int nod;
	for (i = 1; i <= N; ++ i)
	{
		nod = H[1];
		H[1] = H[hsz--];
		combheap (1);

		for (j = 1; j <= lv[nod][0]; ++ j)
			if (dist[nod] + cost[nod][j] < dist[lv[nod][j]])
			{
				dist[lv[nod][j]] = dist[nod] + cost[nod][j];
				update (ind[lv[nod][j]]);
			}
	}
}

void solve ()
{
	dijkstra (1);

	int i;
	for (i = 2; i <= N; ++ i)
		printf ("%d ", dist[i] >= INF ? 0 : dist[i]);
	printf ("\n");
}

int
 main ()
{
	freopen ("dijkstra.in", "rt", stdin);
	freopen ("dijkstra.out", "wt", stdout);

	read ();
	solve ();

	return 0;
}