#include <stdio.h>
#include <vector>
#include <utility>
#define NMax 50010
using namespace std;

const char IN[]="dijkstra.in",OUT[]="dijkstra.out";

int N,M,L;
int d[NMax];
int h[NMax], p[NMax];
bool visit[NMax];
vector<pair<int,int> > ad[NMax];

void schimb(int &a,int &b){
	int tmp=a;a=b;b=tmp;
}

void change(int *h,int p1,int p2){
	p[h[p1]]=p2;
	p[h[p2]]=p1;
	schimb(h[p1],h[p2]);
}

void push(int *h,int v)
{
	if (p[v]) return;
	
	int poz;
	h[++L]=v;
	p[v]=L;
	
	for (poz=L;poz>1 && d[h[poz]]<d[h[poz/2]];poz/=2)
		change(h,poz,poz/2);
}

void remake(int *h,int p)
{
	int min,l=2*p,r=2*p+1;
	min=p;
	if (l<=L && d[h[l]]<d[h[min]]) min=l;
	if (r<=L && d[h[r]]<d[h[min]]) min=r;
	if (min!=p){
		change(h,min,p);
		remake(h,min);
	}
}

void pop(int *h,int x)
{
	int poz;
	for (poz=p[x];poz>1;poz/=2)
		change(h,poz,poz/2);
	change(h,1,L);
	h[L]=0;
	--L;
	remake(h,1);
	p[x]=0;
}

void up_heap(int *h,int v)
{
	int poz;
	for (poz=p[v];poz>1 && d[h[poz]]<d[h[poz/2]];poz/=2)
		change(h,poz,poz/2);
}

void dijkstra(int start)
{
	int x;
	d[start]=0;
	visit[start]=true;
	push(h,start);
	
	while (L>0)
	{
		x=h[1];
		pop(h,x);
		visit[x]=true;
		
		for (vector<pair<int,int> >::iterator it=ad[x].begin();it<ad[x].end();++it)
			if ( !visit[it->first] )
			{
				if ( d[it->first]==-1 || d[x]+it->second<d[it->first])
					d[it->first]=d[x]+it->second;
				if (!p[it->first])
					push(h,it->first);
				else
					up_heap(h,it->first),
					remake(h,it->first);
			}
	}
}

void init(){
	for (int i=0;i<N;++i) d[i]=-1;
}

int main()
{
	int i,x,y,c;
	freopen(IN,"r",stdin);
	scanf("%d%d",&N,&M);
	for (i=0;i<M;++i)
	{
		scanf("%d%d%d",&x,&y,&c);
		ad[x-1].push_back( make_pair(y-1,c) );
	}
	fclose(stdin);
	
	init();
	dijkstra(0);
	
	freopen(OUT,"w",stdout);
	for (i=1;i<N;++i)
		printf("%d ",d[i]!=-1 ? d[i] : 0);
	printf("\n");
	fclose(stdout);
	
	return 0;
}