#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);
         
        //if(nod1==r) d[nod2]=cost,t[nod2]=r;
        //if(nod2==r) d[nod1]=cost,t[nod1]=r;
    }
}
 
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 st,dr,i;
    int poz1=2*r,poz2=2*r+1;
     
    if(poz1<=k)
    {
        st=x[poz1];
        if(poz2<=k)
            dr=x[poz2];
        else
            dr=-1;
         
        if(d[st]<d[dr] || dr==-1) i=poz1;
        else
            i=poz2;
         
        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;
   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]);
			  /* else
			   {
				   x[++nh]=p->inf;
				   poz[x[nh]]=nh;
				   HeapUp(nh);
			   }*/
           }
            
           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;
}