#include <fstream>
#include <set>
#include <vector>
#define DIMN 50010
#define INF 1000000000
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,D[DIMN];
int V[DIMN];

set <pair<int,int> > S;
vector <pair<int,int> > L[DIMN];


int main(void){
    register int i,j,x,y,c,val,valvecin,nod,nodvecin;
    pair<int,int> q;

    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>x>>y>>c;
        L[x].push_back(  make_pair(c,y)  );

    }

    for (i=2;i<=n;i++)
        D[i] = INF;

    S.insert(make_pair(0,1));

    while (!S.empty()) {
//        pair<int,int> q = *S.begin();
        val = S.begin()->first;
        nod = S.begin()->second;
        S.erase(S.begin());
        if (V[nod] == 1)
            continue;
        for (i=0;i<L[nod].size();i++) {
            nodvecin = L[nod][i].second;
            valvecin = L[nod][i].first;
            if (D[nodvecin] > D[nod] + valvecin) {
                D[nodvecin] = D[nod] + valvecin;
                S.insert(make_pair(D[nodvecin],nodvecin));
            }
        }
        V[nod] = 1;


    }

    for(i=2;i<=n;i++){
        if(D[i]==INF)
            g<<"0 ";
        else
            g<<D[i]<<" ";
    }

    f.close();
    g.close();
    return 0;
}