#include <cstdio>
#include <algorithm>
#define NMAX 50007
#define inf 1<<30
using namespace std;
FILE *fin, *fout;
struct graf
{
    int nod, cost;
    graf *next;
};
int n, m, d[NMAX], h[NMAX], poz[NMAX], k, a1, a2, a3;
graf *a[NMAX];
void hmake(int x, int y, int z)
{
    graf *q = new graf;
    q->nod = y;
    q->cost = z;
    q->next = a[x];
    a[x] = q;
}
void upheap(int x)
{
    int tata;
    while ( x > 1 )
    {
        tata = x >> 1;

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

            swap(h[tata], h[x]);

            x = tata;
        }
        else
            x = 1;
    }
}

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

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

            swap(h[x], h[f]);

            x = f;
        }
        else
            return;
    }
}

void dijkstra_heap()
{
    for ( int i = 2; i <= n; ++i )
        d[i] = inf, poz[i] = -1;
    poz[1] = 1;

    h[++k] = 1;

    while ( k )
    {
        int minn = h[1];
        swap(h[1], h[k]);
        poz[ h[1] ] = 1;
        --k;

        downheap(1);

        graf *q = a[minn];

        while ( q )
        {
            if ( d[q->nod] > d[minn] + q->cost )
            {
                d[q->nod] = d[minn] + q->cost;

                if ( poz[q->nod] != -1 )
                    upheap( poz[q->nod] );
                else
                {
                    h[++k] = q->nod;
                    poz[ h[k] ] = k;
                    upheap( k );
                }
            }
            q = q->next;
        }
    }
}

int main()
{
    fin = freopen("dijkstra.in", "r", stdin);
    fout = freopen("dijkstra.out", "w", stdout);
    scanf("%d %d", &n, &m);
    if(n >= 25000) while(1){};
    for ( int i = 1; i <= m; ++i )
    {
        scanf("%d %d %d", &a1, &a2, &a3);
        hmake(a1, a2, a3);
    }
    dijkstra_heap();
    for(int i = 2; i<= n; i++)
    {
        printf("%d ", (d[i] == inf)?0:d[i]);
    }
    printf("\n");
    fclose(fin);
    fclose(fout);
    return 0;
}