#include<fstream>
#include<vector>
#define DIM 50003
#define INF 9999999
using namespace std;
int n, m2, i, j, D[50003], m[50003], x, y, z, k, minim, vecin, nrm;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

vector< pair<int,int> > L[DIM];
int main(){
    in>>n>>m2;
    for(;m2--;){
        in>>x>>y>>z;
        L[x].push_back(make_pair(y, z));
        //L[y].push_back(make_pair(x, z));
    }
    D[1]=0;
    for(i=2; i<=n; i++)
        D[i]=INF;
    while(nrm<=n){
        minim = INF;
        for(i=1; i<=n; i++){
            if(D[i]<minim && m[i] == 0){
                minim=D[i];
                k=i;
            }
        }
        if (minim == INF)
            break;

        m[k]=1;
        nrm++;
        for(i=0; i<L[k].size(); i++){
            vecin=L[k][i].first;
            if(D[vecin]>D[k]+L[k][i].second){
                D[vecin]=D[k]+L[k][i].second;
            }
        }
    }
    for(i=2; i<=n; i++)
        (D[i]!=INF)?(out<<D[i]<<" "):(out<<"0 ");
return 0;
}