#include <fstream>
using namespace std;

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

struct graf
{ int nod, cost; graf *next; };

int n, m;
graf *a[50001];
int d[50001], h[50001], poz[50001], k;

void add(int where, int what, int cost)
{
    graf *q = new graf;
    q->nod = what;
    q->cost = cost;
    q->next = a[where];
    a[where] = q;
}

void read()
{
    in>>n>>m;

    int x, y, z;
    for ( int i = 1; i <= m; i++ )
    {
        in>>x>>y>>z;
        add(x, y, z);
    }
}

void swap(int x, int y)
{
    int t = h[x];
    h[x] = h[y];
    h[y] = t;
}

void upheap(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;

            swap(tata, what);

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

void downheap(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;

            swap(what, f);

            what=f;
        }
        else return;
    }
}

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

    h[++k] = 1;

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

        downheap(1);

        graf *q = a[min];

        while ( q )
        {
            if ( d[q->nod] > d[min] + q->cost )
            {
                d[q->nod] = d[min] + 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()
{
    read();
    dijkstra_heap();

    for (int i=2; i<=n; i++)
        out<< (d[i] == 1<<30 ? 0 : d[i])<<' ';

    return 0;
}