#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const long N = 50001, INF = 2000000000;

struct Edge {
    long x, c;
};

vector <Edge> v[N];
queue <Edge> q;
long u, poz [N], l [N], h [N];

void read (long &n, long &m) {
    long i, x, y, c;
    Edge temp;
    in >> n >> m;
    for (i = 1; i <= m; i ++) {
        in >> x >> y >> c;
        temp.x = y;
        temp.c = c;
        v [x].push_back (temp);
    }
}

void reset (const long &n) {
    long i;
    for (i = 2; i <= n; i ++) {
        poz [i] = -1;
        l [i] = INF;
    }
}

void percolate (long x) {
    long father, aux;
    while (x > 1) {
        father = x >> 1;
        if (l [h [father]] > l [h [x]]) {
            poz [h [father]] = x;
            poz [h [x]] = father;
            aux = h [father];
            h [father] = h [x];
            h [x] = aux;
            x = father;
        }
        else break;
    }
}

void sift (long x) {
    long left, right, mini, son, aux, value_left, value_right;
    while (x <= u) {
        left = x << 1;
        right = left + 1;
        if (left <= u) {
            son = left;
            if (right <= u && l [h [right]] < l [h [left]])
                son = right;
        }
        else break;
        if (l [h [son]] < l [h [x]]) {
            poz [h [son]] = x;
            poz [h [x]] = son;
            aux = h [son];
            h [son] = h [x];
            h [x] = aux;

            x = son;
        }
        else break;
    }
}

void pop () {
    h [1] = h [u];
    poz [h [1]] = 1;
    u --;
    sift (1);
}

void insert (long x) {
    h [++ u] = x;
    poz [h [u]] = u;
    percolate (u);
}


void solve (const long &n, const long &m) {
    long i, p, d;
    vector <Edge> :: iterator it;
    Edge node;

    reset (n);
    h [++ u] = 1;
    poz [1] = 1;
    l [1] = 0;
    while (u) {
        p = h [1];
        pop ();
        for (it = v [p].begin (); it != v [p].end(); ++it) {
            node = *it;
            d = node.c + l [p];
            if (d < l [node.x]) {
                l [node.x] = d;
                if (poz [node.x] != -1)
                    percolate (poz [node.x]);
                else
                    insert (node.x);
            }
        }
    }

    for (i = 2; i <= n; i ++) {
        if (l [i] != INF)
        out << l [i] << " ";
        else out << "0" << " ";
        }
    out << "\n";
}

int main () {
    long n, m;
    read (n, m);
    solve (n, m);
    return 0;
}