#include<fstream>
#define inf 98765432
#define maxm 250005
#define maxn 50005
using namespace std;
ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");

int a[maxm],b[maxm],c[maxm];
int d[maxn];
int i,n,m;

void dijkstra(int sursa){
     int i; short int ok;
     
     for(i=1;i<=n;i++) d[i]=inf;
     
     d[sursa]=0; ok=1;
     
     while(ok){
               ok=0;
               for(i=1;i<=m;i++)
                 if (d[a[i]]!=inf && d[b[i]]==inf || d[a[i]]+c[i]<d[b[i]])
                 {
                  ok=1;
                  d[b[i]]=d[a[i]]+c[i];
                 }
              }
     
}

int main(){
    fi>>n>>m;
    
    for(i=1;i<=m;i++) fi>>a[i]>>b[i]>>c[i];
    
    dijkstra(1);
    
    for(i=2;i<=n;i++)
       if (d[i]==inf) fo<<0<<" ";
       else fo<<d[i]<<" ";
    
    fi.close();
    fo.close();
    return 0;
}