#include<cstdio>
#define INF 0x3f3f3f3f
using namespace std;

typedef struct nod
{
	int inf,c;
	nod *urm;
} NOD;
typedef NOD *graf[50010];

void readData(int &n, int &m, graf);
void append(NOD *&x, int inf, int c);
void percolate(int h[], int n, int d[], int pos[], int i);
void swp(int &x, int &y);
void sift(int h[], int n, int d[], int pos[], int i);
void initialize(int h[], int d[], int pos[], int n);
void dijkstra(graf G, int h[], int d[], int pos[], int n);
void writeData(int d[], int n);



int main()
{
	graf G;
	int n, m;
	int heap[50010], nh = 0, d[50010], pos[50010];
	readData(n, m, G);
	initialize(heap, d, pos, n);
	dijkstra(G, heap, d, pos, n);
	writeData(d, n);
}

void readData(int &n, int &m, graf G)
{
	freopen("dijkstra.in", "r", stdin);
	scanf("%d %d", &n, &m);
	int i, x, y, c;
	for(i = 0; i < n; i++)
		G[i] = NULL;
	for(i = 0; i < m; i++)
	{
		scanf("%d %d %d", &x, &y, &c);
		append(G[x], y, c);
	}
}

void append(NOD *&x, int inf, int c)
{
	NOD *p = new NOD;
	p->inf = inf;
	p->c = c;
	p->urm = x;
	x = p;
}

void swp(int &x, int &y)
{
	x = x^y;
	y = x^y;
	x = x^y;
}

void percolate(int h[], int n, int d[], int pos[], int i)
{
	int ok = 1;
	while(ok && i > 1)
	{
		if(d[h[i]] < d[h[i/2]])
		{
			swp(h[i], h[i/2]);
			swp(pos[h[i]], pos[h[i/2]]);
			i /= 2;
		}
		else
		{
			ok = 0;
		}
	}
	sift(h, n, d, pos, i);
}

void sift(int h[], int n, int d[], int pos[], int i)
{
	int ok = 1;
	while(ok && i < n)
	{
		if(d[h[2*i]] < d[h[i]] &&  2*i <= n)
		{
			if(d[h[2*i + 1]] < d[h[i]] && 2*i + 1 <= n)
			{
				int aux = d[h[2*i]] < d[h[2*i + 1]] ? 2*i : 2*i + 1;
				swp(h[i], h[aux]);
				swp(pos[h[i]], pos[h[aux]]);
				i = aux;
			}
			else
			{
				swp(h[i], h[2*i]);
				swp(pos[h[i]], pos[h[2*i]]);
				i = 2*i;
			}
		}
		else
			if(d[h[2*i + 1]] < d[h[i]] && 2*i + 1 <= n)
			{
				swp(h[i], h[2*i + 1]);
				swp(pos[h[i]], pos[h[2*i + 1]]);
				i = 2*i + 1;
			}
			else
			{
				ok = 0;
			}
	}
}

void initialize(int h[], int d[], int pos[], int n)
{
	int i;
	for(i = 1; i <= n; i++)
	{
		h[i] = i;
		pos[i] = i;
		d[i] = INF;
	}
	d[1] = 0;
}

void dijkstra(graf G, int h[], int d[], int pos[], int n)
{
	int nh = n;
	while(nh)
	{
		int x = h[1];
		swp(h[1], h[nh]);
		swp(pos[1], pos[nh]);
		nh--;
		sift(h, nh, d, pos, 1);
		for(NOD *i = G[x]; i; i = i->urm)
			if((d[x] + i->c) < d[i->inf])
			{
				d[i->inf] = d[x] + i->c;
				percolate(h, nh, d, pos, pos[i->inf]);
			}
	}
}

void writeData(int d[], int n)
{
	freopen("dijkstra.out", "w", stdout);
	int i;
	for(i = 2; i <= n; i++)
	{
		printf("%d ", d[i] < INF ? d[i] : 0);
	}
}