#include<fstream>
#define MAXX 999999999
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct nod{int inf,c; nod *urm;};
nod *l[50002];

int d[50002],t[50002],x[50002],poz[50002],n,m,nh,r;



void add(int p1,int p2,int cost)
{
	nod *q;
	
	q=new nod;
	q->inf=p2;
	q->c=cost;
	
	q->urm=l[p1];
	l[p1]=q;
}




void citire()
{
	int p1,p2,cost,i;
	
	fin>>n>>m;
	r=1;
	
	for(i=1;i<=m;i++)
	{
		fin>>p1>>p2>>cost;
		add(p1,p2,cost);
	}
	
	fin.close();
}




void swap(int i,int j)
{
	int aux;
	
	aux=x[i];
	x[i]=x[j];
	x[j]=aux;
	
	poz[x[i]]=i;
	poz[x[j]]=j;
}





void HeapUP(int k)
{
	int i;
	
	if(k<=1)
		return ;

	i=k/2;
	
	if(d[x[k]]<d[x[i]])
	{
		swap(i,k);
		HeapUP(i);
	}
}




void BuildH(int k)
{
	int i;
	
	for(i=1;i<=n;i++)
		HeapUP(i);
}




void HeapDW(int r,int k)
{
	int st,dr,i;
	
	if(2*r<=k)
	{
		st=x[2*r];
		
		if(2*r+1<=k)
			dr=x[2*r+1];
		else
			dr=-2;
	
	if(d[st]<d[dr] || dr==-2)
		i=2*r;
	else
		i=2*r+1;
	
	
	if(d[x[r]]>d[x[i]])
	 {
		swap(r,i);
		HeapDW(i,k);
	 }
	else
		return;
	
	}
}




int scoate_heap()
{
	swap(1,nh);
	poz[x[nh]]=0;
	nh--;
	HeapDW(1,nh);
	
	return x[nh+1];
}




void Dijkstra()
{
	int i,k;
	nod *p;
	
	for(i=1;i<=n;i++)
	{
		d[i]=MAXX;
		x[i]=i;
		poz[i]=i;
	}
	
	
	d[r]=0; nh=n; 
	
    BuildH(n);
	
	
	while(nh>0)
	{
		k=scoate_heap();
        
		p=l[k];
		
		while(p)
		{
			if(d[p->inf] > d[k]+p->c && poz[p->inf])
			{
				d[p->inf]=d[k]+p->c;
				t[p->inf]=k;
				
				HeapUP(poz[p->inf]);
			}
		
			p=p->urm;
		}
	}
}





void afis()
{
	int i;
	
	for(i=1;i<=n;i++)
		if(i!=r)
		{
		 if(d[i]<MAXX)
			fout<<d[i]<<" ";
		else
			fout<<0<<" ";
		}
		
	fout.close();
}




int main()
{
	citire();
	Dijkstra();
	afis();
	
	return 0;
}