#include<fstream>
#include<cstring>
#define nmax 50005
#define mmax 250005
using namespace std;

int a[mmax],b[mmax],c[mmax],d[nmax];

int main(void){
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    int i,j,k,n,m; bool change=1;
    fin>>n>>m;
    for(i=1;i<=m;++i)fin>>a[i]>>b[i]>>c[i]; 
    fin.close();
    memset(d,-1,sizeof(d)); d[1]=0;
    while(change){
            change = 0;
            for(i=1;i<=m;++i)
              if(d[a[i]]!=-1 && (d[a[i]]+c[i]<d[b[i]] || d[b[i]]<0)){
                                      d[b[i]]=d[a[i]]+c[i];
                                      if(!change)change = 1;
                                      }            
            }
    for(i=2;i<=n;++i)
      if(d[i]>=0)fout<<d[i]<<' ';
        else fout<<'0'<<' ';         
 return 0;   
}