#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cassert>
#include <utility>
#include <set>
#define mp make_pair
#define Dp pair<int,int>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

const int f_mare = 2e9;
int n, m, i, j, x, y, c;
int d[50005];
vector<Dp > ls[50005];

int main() {
    f >> n >> m;
    /*assert(1 <= n && n <= 50000);
    assert(1 <= m && m <= 250000);*/

    for (i = 1; i <= m; i++) {
        f >> x >> y >> c;
        /*assert(1 <= x && y<= n);
        assert(1 <= y && y<= n);
        assert(0 <= c && c<= 20000);*/
        ls[x].push_back(mp(y, c));
    }
    for(i = 2; i<=n;d[i] = f_mare, i++);
    set <Dp > H;
    d[1] = 0;
    H.insert(mp(1, 0) );
    int cc;
    while (!H.empty()) {
        x = H.begin() -> first;
        cc = H.begin() -> second;
        H.erase(H.begin());

        for (vector<Dp >::iterator it = ls[x].begin(); it != ls[x].end(); it++) {
            y = it -> first;
            c = it -> second;
            if (d[x]+c < d[y]) {
                if (d[y] != f_mare)
                    H.erase(H.find(mp(y, d[y])));
                d[y] = d[x]+c;
                H.insert(mp(y, d[y]));
            }
        }
    }

    for (i = 2; i <= n; i++)
        g << (d[i] == f_mare ? 0:d[i]) << ' ';

    return 0;
}