#include<fstream.h>

#define xn 50001
#define xm 250001

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

int a[xm],b[xm],c[xm],t[xn],d[xn],n,m;

void bellman(int s)
{
     int ok,nr,i;
     
     memset(d,0x3f3f3f,sizeof(d));
     
     d[s]=0;
     
     for(nr=ok=1 ; nr<n &&ok ; nr++)
       for(i=1;i<=m;i++)
          if(d[b[i]]>d[a[i]]+c[i])
            d[b[i]]=d[a[i]]+c[i],t[b[i]]=1,ok=1;
}

int main()
{
    int i;
    fin>>n>>m;
    for(i=1;i<=m;i++)
      fin>>a[i]>>b[i]>>c[i];
    
    bellman(1);
    
    for(i=2;i<=n;i++)
      if(t[i])
        fout<<d[i]<<' ';
      else
        fout<<"0 ";
    
    fout<<'\n';
    fout.close();
    return 0;
}