#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("dijkstra_try2.in");
ofstream fout("dijkstra_try2.out");

const int nMax=5000;
int oo=(1<<30);
int n,m,A[nMax][nMax],D[nMax],T[nMax],S[nMax];



void citire(){

     for(int i=1;i<=m;i++){
        int x,y,c;
        fin>>x>>y>>c;
        A[x][y]=c;
     }

}

void init(){
   int i,j;
   for(i=1;i<=n;i++){S[i]=0;T[i]=0;
   for(j=1;j<=n;j++)if(i==j)A[i][j]=0;
                    else A[i][j]=oo;
}}

void distDeLaNodlaRest(int nod){
     for(int i=1;i<=n;i++)D[i]=A[nod][i];
}
void stabilireCopii(int nod){
     for(int i=1;i<=n;i++)if(A[nod][i]!=nMax && nod!=i)T[i]=nod;
}

void dijkstra(int nodStart){


       S[nodStart]=1;
       distDeLaNodlaRest(nodStart);
       stabilireCopii(nodStart);
       for(int i=1;i<n;i++){
           int nodCurent,minim=oo;
           for(int j=1;j<=n;j++){
            if(S[j]==0)
            if(D[j]<minim){minim=D[j];nodCurent=j;}
           }
           S[nodCurent]=1;
           for(int j=1;j<=n;j++)if(S[j]==0)
           if(D[j]>D[nodCurent]+A[nodCurent][j]){D[j]=D[nodCurent]+A[nodCurent][j];T[j]=nodCurent;}

       }
}

int main()
 {  fin>>n>>m;
     init();
     citire();
     dijkstra(1);
     for(int i=2;i<=n;i++)fout<<D[i]<<" ";




    return 0;
}