#include<fstream>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
using namespace std;
long n,m;
struct muchie {long x,y,c;} a[250001]; 
long d[50001];
int main()
{       
    long i;
    fin>>n>>m;
    for(i=1;i<=m;i++)
        { fin>>a[i].x>>a[i].y>>a[i].c;
          if(a[i].x==1) d[a[i].y]=a[i].c;  
        }    
    for(i=1;i<=n;i++)  
         if(d[i]==0) d[i]=250001;  
         
     
    int gata=0; 
    while(!gata)
     {
         gata=1;
         for(int i=1; i<=m; i++)
            if(d[a[i].y]>d[a[i].x]+a[i].c)
             { gata=0;
               d[a[i].y]=d[a[i].x]+a[i].c;
             }
      }         
       
 
    for(i=2;i<=n;i++)
        if(d[i]>=32000) fout<<"0 ";
             else fout<<d[i]<<" ";
    return 0;
}