#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 *q = a[mn];

        while ( q )
        {
            if ( d[q->to] > d[mn] + q->length )
            {
                d[q->to] = d[mn] + q->length;

                if ( poz[q->to] != -1 )
                    percolate( poz[q->to] );
                else
                {
                    h[++k] = q->to;
                    poz[ h[k] ] = k;
                    percolate( k );
                }
            }
            q = q->next;
        }
    }
    for(int i = 2; i <= n; i ++) {
        cout << d[i] << " ";
    }
    cout << "\n";
    return 0;
}