#include<fstream>
#include<vector>
#define INF 2000000000

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



vector< pair<int,int> > v[50005] ;
int d[50005],f[50005];
int n,m,i,x,y,z,ok,nod,vecin,minim, cost;
int main(){
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>x>>y>>z;
        v[x].push_back(make_pair(y,z));
    }
    for(i=2;i<=n;i++){
        d[i]=INF;
    }
    d[1]=0;

    ok=0;
    nod=1;
    while(ok==0){
        minim = INF;
        for (i=1;i<=n;i++)
            if (f[i] == 0 && d[i] < minim) {
                minim = d[i];
                nod = i;
            }

        if (minim == INF)
            break;

        f[nod] = 1;

        for (i=0;i<v[nod].size();i++) {
            vecin = v[nod][i].first;
            cost = v[nod][i].second;

            if (f[vecin] == 0 && d[vecin] > d[nod] + cost)
                d[vecin] = d[nod] + cost;
        }

    }
    for(i=2;i<=n;i++){
        fout<<(d[i] == INF ? 0 : d[i])<<" ";
    }
    return 0;
}