#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 what)
{
    int tata;
    while ( what > 1 )
    {
        tata = what >> 1;

        if ( d[ h[tata] ] > d[ h[what] ] )
        {
            poz[ h[what] ] = tata;
            poz[ h[tata] ] = what;

            int aux = h[tata];
            h[tata] = h[what];
            h[what] = aux;

            what = tata;
        }
        else
            what = 1;
    }
}

void sift(int what)
{
    int f;
    while ( what <= k )
    {
        f = what;
        if ( (what<<1) <= k )
        {
            f = what << 1;
            if ( f + 1 <= k )
                if ( d[ h[f + 1] ] < d[ h[f] ] )
                    ++f;
        }
        else
            return;

        if ( d[ h[what] ] > d[ h[f] ] )
        {
            poz[ h[what] ] = f;
            poz[ h[f] ] = what;

            int aux = h[f];
            h[f] = h[what];
            h[what] = aux;

            what = f;
        }
        else
            return;
    }
}

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;
}