#include <cstdio>
#include <cstdlib>
#include <cstring>

#define SIZE 50005

long long heap[SIZE], heapSize;
long long d[SIZE], dheap[SIZE];
long long n, m;


struct nod 
{
	long long dest, c;

	struct nod * next;
};

struct nod * nds[SIZE];

void add(long long from, long long to, long long c)
{
	struct nod * cnod;

	cnod = (nod *) malloc(sizeof(struct nod));

	cnod->dest = to;
	cnod->c = c;	
	cnod->next = nds[from];

	nds[from] = cnod;

}

void read()
{	
	long long i, t1, t2, t3;

	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);

	scanf("%lld%lld", &n, &m);

	for(i = 0; i < m; i++)
	{
		scanf("%lld%lld%lld", &t1, &t2, &t3);

		add(t1, t2, t3);
//		add(t2, t1, t3);
	}
	
}

int main()
{
	long long i, j, from;
	
	struct nod * cnod;

	read();

	for(i = 1; i <= n; i++)
		d[i] = 1 << 30;

	d[1] = 0;

	for(j = 1; j <= n; j++)
	{
	for(i = 1; i <= n; i++)
	{
		cnod = nds[i];
		
		while(cnod)
		{
			if(d[cnod->dest] > d[i] + cnod->c)
			{
				d[cnod->dest] = d[i] + cnod->c;
			}

			cnod = cnod->next;
		}
	}
/*
	for(i = 1; i <= n; i++)
	{
		fprintf(stderr, "%d ", d[i]);
	}
	fprintf(stderr, "\n\n");
*/
	}

	for(i = 2; i <= n; i++)
	{
		d[i] == 1 << 30 ? printf("0 ") : printf("%lld ", d[i]);
	}

	return 0;
}