#include<fstream>
#include<vector>
using namespace std;
ifstream in ("dijkstra.in");
ofstream out ("dijkstra.out");
int d[50005],poz[50005],hz[50005];
int sz,n,m,a,b,c;
struct str {
    int val, poz;
}heap[50005];
vector<pair<int,int> >v[50005];
void up (int p) {
    while (p > 1 && heap[p].val < heap[p/2].val) {
        swap (heap[p],heap[p/2]);
        swap (poz[heap[p].poz],poz[heap[p/2].poz]);
        p /= 2;
    }
    return;
}
void down (int p) {
    while (p*2 <= sz) {
        int t = p*2;
        if (t < sz && heap[t+1].val < heap[t].val) {
            t ++;
        }
        if (heap[p].val > heap[t].val) {
            swap (heap[p], heap[t]);
            swap (poz[heap[p].poz], poz[heap[t].poz]);
            p = t;
        }
        else {
            break;
        }
    }
    return;
}
void elimina () {
    hz[heap[1].poz] = 1;
    swap (heap[1], heap[sz]);
    swap (poz[heap[1].poz],poz[heap[sz].poz]);
    sz --;
    down (1);
    return;
}
int main (void) {
    in >> n >> m;
    for (int i = 1; i <= m; i ++) {
        in >> a >> b >> c;
        v[a].push_back (make_pair(b,c));
    }

    sz = n;
    for (int i = 1; i <= n; i ++) {
        heap[i] = {1000000000,i};
        poz[i] = i;
    }
    heap[1].val = 0;

    for (int i = 1; i <= n; i ++) {
        int nod = heap[1].poz;
        int val = heap[1].val;
        d[nod] = val;
        elimina();
        for (int j = 0; j < v[nod].size(); j ++) {
            int vecin = v[nod][j].first;
            int cost = v[nod][j].second;
            if (hz[vecin] == 0 && heap[poz[vecin]].val > val + cost) {
                heap[poz[vecin]].val = val + cost;
                up (poz[vecin]);
            }
        }
    }

    for (int i = 2; i <= n; i ++){
        if (d[i] == 1000000000) d[i] = 0;
        out << d[i] <<" ";
    }
    return 0;
}