#include<stdio.h>
#define MAX 50001
#define INF 0x3f3f3f
int X = 1, N, M,order[MAX],D[MAX],nrelem;
struct HEAP
{
	int val,order;
}heap[MAX],aux;
struct graf
{
	int nod,c;
	graf*next;
}*A[MAX],*q;
void add(int x,int y,int c)
{
	q = new graf;
	q->nod = y;
	q->c = c;
	q->next = A[x];
	A[x] = q;
}
int left_son(int x){return 2*x;}
int right_son(int x){return 2*x+1;}
int father(int x){return x/2;}
void swap(int x,int y)
{
	order[heap[x].order] = y;
	order[heap[y].order] = x;
	aux = heap[x];
	heap[x] = heap[y];
	heap[y] = aux;
}
void sift(int x)
{
	int son;
	do
	{
		son = 0;
		if(left_son(x)<=nrelem)
		{
			son = left_son(x);
			if(right_son(x)<=nrelem && heap[right_son(x)].val < heap[son].val)
				son = right_son(x);
		}
		if(heap[x].val <= heap[son].val)
			son = 0;
		if(son)
		{
			swap(x,son);
			x = son;
		}
	}while(son);	
}
void percolate(int x)
{
	while(father(x) && heap[father(x)].val > heap[x].val)
	{
		swap(x,father(x));
		x = father(x);
	}
}
void cut(int x)
{
	heap[x] = heap[nrelem--];
	sift(x);
	if(father(x) && heap[father(x)].val > heap[x].val)
		percolate(x);
}
void update(int x,int val)
{
	heap[x].val = val;
	sift(x);
	if(father(x) && heap[father(x)].val > heap[x].val)
		percolate(x);
}
void init()
{
	int i;
	nrelem = N;
	for(i=1;i<=N;++i)
	{
		D[i] = heap[i].val = INF;
		order[i] = heap[i].order = i;
	}
	D[X] = 0;
	update(X, 0);
	cut(order[X]);
}
void make(int x)
{
	q = A[x];
	while(q)
	{
		if(q->c + D[x] < D[q->nod])
		{
			D[q->nod] = q->c + D[x];
			update(order[q->nod], D[q->nod]);
		}
		q = q->next;
	}
}
int main()
{
	FILE*f = fopen("dijkstra.in","r");
	fscanf(f,"%d%d",&N,&M);
	init();
	int i,A,B,C,p;
	for(i=1;i<=M;++i)
	{
		fscanf(f,"%d%d%d",&A,&B,&C);
		if(A == X)
		{
			D[B] = C;
			update(order[B], C);
		}
		else add(A,B,C);
	}
	fclose(f);
	i = 1;
	while(i <= N)
	{		
		if(heap[1].val == INF)
		{i = N+1;continue;}
		p = heap[1].order;
		cut(1);
		make(p);
		++i;
	}
	FILE*g = fopen("dijkstra.out","w");
	for(i=2;i<=N;++i)
	{
		if(D[i] == INF)D[i] = 0;
		fprintf(g,"%d ",D[i]);
	}
	fclose(g);
	return 0;
}