#include <bits/stdc++.h>

using namespace std;

struct node{
node *next;
int to;
int length;
};
node *a[50005];
long long d[50005];
int poz[50005];
int h[50005], k;

void percolate(int i) {
    int tata;
    while(i > 1) {
        tata = i >> 1;
        if(d[h[tata]] > d[h[i]]) {
            poz[h[tata]] = i;
            poz[h[i]] = tata;
            int aux = h[i];
            h[i] = h[tata];
            h[tata] = aux;
            i = tata;
        }
        else i = 1;
    }
}

void sift(int i) {
    int son;
    while(i <= k) {
        if(i << 1 <= k) {
            son = i << 1;
            if(son < k)
                if(d[h[son]] > d[h[son + 1]])
                    son ++;
            if(d[h[son]] < d[h[i]]) {
                poz[h[son]] = i;
                poz[h[i]] = son;
                int aux = h[son];
                h[son] = h[i];
                h[i] = aux;
                i = son;
            }
            else i = k + 1;
        }
        else i = k + 1;
    }
}

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; i ++) {
        int from, to, length;
        cin >> from >> to >> length;
        node *one = new node;
        one->to = to;
        one->length = length;
        one->next = a[from];
        a[from] = one;
    }

    for(int i = 2; i <= n; i ++) {
        d[i] = 50000005;
        poz[i] = -1;
    }
    poz[1] = 1;
    h[++ k] = 1;
    while(k) {
        int mn = h[1];
        h[1] = h[k];
        poz[h[1]] = 1;
        k --;
        sift(1);
        node *cur = a[mn];
        while(cur) {
            if(d[cur->to] > d[mn] + cur->length) {
                d[cur->to] = d[mn] + cur->length;
                if(poz[cur->to] != -1) {
                    percolate(poz[cur->to]);
                }
                else {
                    k ++;
                    h[k] = cur->to;
                    poz[h[k]] = k;
                    percolate(k);
                }
            }
            cur = cur->next;
        }
    }

    for(int i = 2; i <= n; i ++) {
        cout << d[i] << " ";
    }
    cout << "\n";
    return 0;
}