#include <bits/stdc++.h>
using namespace std;

const int NMAX = 250005;

struct PII {
    int u, w;

    PII() {}
    PII(int _u, int _w) {
        u = _u; //Nod
        w = _w; //Weight
    }

    bool operator <(PII arg) const {
        return w < arg.w;
    }
    bool operator >(PII arg) const {
        return w > arg.w;
    }
};

vector<PII> g[NMAX];
int         d[NMAX];

void dijkstra(void) {
    priority_queue<PII, vector<PII>, greater<PII> > q;
    PII tmp;

    q.push(PII(1, 1));

    while(!q.empty()) {
        tmp = q.top();
        q.pop();

        if(!d[tmp.u]) {
            for(auto &i:g[tmp.u]) {
                if(d[i.u])
                    continue;
                q.push(PII(i.u, i.w+tmp.w));
            }
            d[tmp.u] = tmp.w;
        }
    }
}

int main(void) {
    FILE *fi = fopen("dijkstra.in", "r");
    FILE *fo = fopen("dijkstra.out", "w");
    int n, m, u, v, w;

    fscanf(fi,"%d%d",&n,&m);
    for(int i=0; i<m; ++i) {
        fscanf(fi,"%d%d%d",&u,&v,&w);
        g[u].push_back(PII(v, w));
    }

    dijkstra();

    for(int i=2; i<=n; ++i)
        fprintf(fo,"%d ",max(d[i]-1, 0));
    fprintf(fo,"\n");

    fclose(fi);
    fclose(fo);
    return 0;
}