#include<fstream>
using namespace std;
 
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
 
struct nod{int inf,c;nod *urm;};
nod *l[50005];
 
int n,m,r,nh;
int d[50005],t[50005],poz[50005],x[50005];
 
void add(int nod1,int nod2,int cost)
{
    nod *q;
     
    q=new nod;
    q->inf=nod2;
    q->c=cost;
     
    q->urm=l[nod1];
    l[nod1]=q;
}
 
void cit()
{
    int i;
    int nod1,nod2,cost;
     
    fin>>n>>m;
    r=1;
	
    for(i=1;i<=m;i++)
    {
        fin>>nod1>>nod2>>cost;
        add(nod1,nod2,cost);
        //add(nod2,nod1,cost);
    }
}
 
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<=k;i++)
        HeapUp(i);
}
 
void HeapDw(int r,int k)
{
    int i=2*r;
    
    if(i<=k)
    {
        if(i+1<=k)
			if(d[x[i]]>d[x[i+1]]) i++;
		
        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]=999999999;
       x[i]=i;
       poz[i]=i;
    }
	
   d[r]=0; nh=n;
   swap(1,r);
    
   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 print(int k)
{
    if(k>0)
    {
        print(t[k]);
        fout<<k<<" ";
    }
}
 
void afis()
{
    int i;
     
    for(i=1;i<=n;i++)
        if(i!=r)
        {
            //print(i);
            //fout<<"cost="<<d[i];
            //fout<<'\n';
            if(d[i]<999999999)
            fout<<d[i]<<" ";
            else fout<<"0 ";
        }
}   
 
 
 
int main()
{
    cit();
    dijkstra();
    afis();
     
     
    fin.close();
    fout.close();
    return 0;
}