#include<fstream>
#define MAX 50001
using namespace std;
int n,m,d[MAX],X,nrelem,order[MAX],ind;
struct bla
{
	int val,order;
}heap[MAX],aux;
struct graf
{
	int nod,cost;
	graf*next;
}*a[MAX];
int right_son(int x)
{
	return x*2 + 1;
}
int left_son(int x)
{
	return x*2;
}
int father(int x)
{
	return x/2;
}
void sift(int x)
{
	int son;
	do
	{
		son = 0;
		if(left_son(x) <= nrelem)
		{
			son = left_son(x);
			if(right_son(x) <= nrelem && heap[son].val > heap[right_son(x)].val)
				son = right_son(x);
		}
		if(heap[son].val >= heap[x].val)
			son = 0;
		
		if(son)
		{
			order[heap[son].order] = x;
			order[heap[x].order] = son;
			aux = heap[son];
			heap[son] = heap[x];
			heap[x] = aux;
			x = son;
		}
	}while(son);
}
void percolate(int x)
{
	while(heap[father(x)].val > heap[x].val && father(x))
	{
		order[heap[father(x)].order] = x;
		order[heap[x].order] = father(x);
		
		aux = heap[father(x)];
		heap[father(x)] = heap[x];
		heap[x] = aux;
		x = father(x);
	}
}
void cut(int x)
{
	heap[x] = heap[nrelem--];
	sift(x);
	if(heap[father(x)].val > heap[x].val && father(x))
		percolate(x);
}
void update(int x,int val)
{
	heap[x].val = val;
	sift(x);
	if(heap[father(x)].val > heap[x].val && father(x))
		percolate(x);
}
void init()
{
	int i;
	for(i=1;i<=n;++i)
	{
		d[i] = 999999;
		order[i] = i;
		heap[i].order = i;
		heap[i].val = 999999;
	}
	nrelem = n;
	X = 1;
	cut(order[X]);
}
void add(int x,int y,int c)
{
	graf*q = new graf;
	q->nod = y;
	q->cost = c;
	q->next = a[x];
	a[x] = q;
}
void make(int min)
{
	graf*q = 0;
	if(a[min])
	q = a[min];
	int j;
	while(q)
	{
		j = q->nod;
		if(q->cost + d[min] < d[j])
		{
			d[j] = q->cost + d[min];
			update(order[j],d[j]);
		}
		q=q->next;
	}
}
int main()
{
	ifstream f("dijkstra.in");
	f>>n>>m;
	init();
	int x,y,c,i;
	for(i=1;i<=m;++i)
	{
		f>>x>>y>>c;
		if(x == X)
		{
			d[y] = c;
			update(order[y],c);			
		}
		else add(x,y,c);
	}
	f.close();
	d[X] = 0;
	
	int nr = 1;
	while(nr<=n)
	{
		if(heap[1].val == 999999)
		{
			nr = n+1;continue;
		}
		i = heap[1].order;
		cut(1);
		
		make(i);		
		++nr;
	}
	
	ofstream g("dijkstra.out");
	for(i=2;i<=n;++i)
	{
		if(d[i] == 999999){g<<"0 ";continue;}
		g<<d[i]<<" ";
	}
	g.close();
	return 0;
}