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

using namespace std;

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

const long N = 50000, 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 = 0; 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 = 1; 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]]) {
            aux = h [father];
            h [father] = h [x];
            h [x] = aux;
            aux = poz [father];
            poz [father] = poz [x];
            poz [x] = aux;
        }
        else break;
        x = father;
    }
}

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)
            value_left = l [h [left]];
        else value_left = INF;
        if (right <= u)
            value_right = l [h [right]];
        else value_right = INF;
        mini = min(value_left, value_right);
        if (mini == INF)
            break;
        if (mini < h [x]) {
            if (mini == value_left)
                son = left;
            else son = right;
            aux = h [son];
            h [son] = h [x];
            h [x] = aux;
            aux = poz [son];
            poz [son] = poz [x];
            poz [x] = aux;
            x = son;
        }
        else break;
    }
}

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

void insert (long x) {
    h [++ u] = x;
    poz [x] = 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;
    l [u] = 0;
    while (u) {
        p = h [1];
        pop ();
        if (l [p] == INF)
            break;
        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)
                    sift (poz [node.x]);
                else
                    insert (node.x);
            }
        }
    }

    for (i = 2; i <= n; i ++)
        out << l [i] << " ";
    out << "\n";
}

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