#include <iostream>
#include <fstream>
#include <vector>
#define nmax 50010
#define Vmax 100000
using namespace std;
ifstream f("dijkstra2.in");
ofstream g("dijkstra2.out");
vector <int> a[nmax], d[nmax];
int n, m, p, dist[nmax], vis[nmax], vv, pozitie, valoare;
struct arbore {
    int minim,pos,viz;
}arb[3*nmax];
void citire() {
    f >> n >> m;
    int x, y, Cost;
    for (int i = 1; i <= m; i ++) {
        f >> x >> y >> Cost;
        a[x].push_back(y);
        d[x].push_back(Cost);
    }
}
void afisare() {
    for (int i = 1;i <= n;i ++) {
        cout << dist[i] << " ";
    }
}
void Creare(int nod, int st, int dr) {
    if (st == dr) {
        arb[nod].pos = st;
        arb[nod].minim = dist[st];
        arb[nod].viz = vis[st];
    } else {
        int mij = (st + dr) / 2;
        Creare(2*nod,st,mij);
        Creare(2*nod+1,mij + 1, dr);

        if (arb[2*nod+1].viz == 1) {
            arb[nod] = arb[2*nod];
        } else if (arb[2*nod].viz == 1) {
            arb[nod] = arb[2*nod+1];
        } else if (arb[2*nod].minim < arb[2*nod+1].minim) {
            arb[nod] = arb[2*nod];
        } else {
            arb[nod] = arb[2*nod+1];
        }
    }
}
void Adauga(int nod, int st, int dr) {
    if (st == dr) {
        arb[nod].minim = valoare;
        arb[nod].pos = pozitie;
        arb[nod].viz = vv;

    } else {
        int mij = (st + dr) /2;
        if (pozitie <= mij) {
            Adauga(2*nod,st,mij);
        } else {
            Adauga(2*nod+1,mij+1,dr);
        }

        if (arb[2*nod+1].viz == 1) {
            arb[nod] = arb[2*nod];
        } else if (arb[2*nod].viz == 1) {
            arb[nod] = arb[2*nod+1];
        } else if (arb[2*nod].minim < arb[2*nod+1].minim) {
            arb[nod] = arb[2*nod];
        } else {
            arb[nod] = arb[2*nod+1];
        }

    }
}
void rez() {
    int x, y;
    p = 1;
    for (int i = 0; i < a[p].size(); i ++) {
        x = a[p][i];
        y = d[p][i];
        dist[x] = y;
    }
    for (int i = 1;i <= n;i ++) {
        if (dist[i] == 0) {
            dist[i] = Vmax;
        }
    }

    vis[p] = 1;
    dist[p] = 0;

    //afisare();


    Creare(1,1,n);


    for (int i = 1;i < n;i ++) {
        int pmin = arb[1].pos;
        int vmin = arb[1].minim;

        pozitie = pmin;
        valoare = vmin;
        vv = 1;

        Adauga(1,1,n);

        for (int j = 0;j < a[pmin].size(); j ++ ) {
            int x = a[pmin][j];
            int c1 = d[pmin][j];
            if (dist[x] > c1 + vmin && vis[x] == 0 ) {
                valoare = c1 + vmin;
                pozitie = x;
                dist[x] = c1 + vmin;
                vv = 0;
                Adauga(1,1,n);
            }
        }

        //cout << dist[1] << "\n";

    }

    for (int i = 2;i <= n;i ++) {
        if (dist[i] != Vmax) {
            g << dist[i] << " ";
        } else {
            g << "0 ";
        }
    }

}
int main() {
    citire();
    rez();
    return 0;
}