#include<fstream>
#include<vector>
#define inf 2000000000
using namespace std;
vector < pair <int, int> > L[50003];
int n, m2, i, x, y, z, D[50003], minim, vecin, nrm, k, m[50003];
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int main(){
    in>>n>>m2;
    for(;m2--;){
        in>>x>>y>>z;
        L[x].push_back(make_pair(y, z));
    }
    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;
        nrm++;
        m[k]=1;
        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;
}