#include <cstdio>
#include <vector>

#include <cmath>

using namespace std;

#define MAXN 1050

vector <int>vec[MAXN];
vector <int>cost[MAXN];

int heap[MAXN];
int vtoheap[MAXN];
int heaptov[MAXN];
int cost1[MAXN];
bool visited[MAXN];
int v[MAXN];

int nrheap, active;

void HeapSwap( int nod1, int nod2 )
{
    int dummy;

    dummy = heap[nod1];
    heap[nod1] = heap[nod2];
    heap[nod2] = dummy;

    vtoheap[heaptov[nod1]] = nod2;
    vtoheap[heaptov[nod2]] = nod1;

    dummy = heaptov[nod1];
    heaptov[nod1] = heaptov[nod2];
    heaptov[nod2] = dummy;
}

void HeapUp( int nod )
{
    bool ok = 1;
    while ( ok )
    {
        ok = 0;
        if ( heap[nod] < heap[nod/2] )
        {
            HeapSwap( nod, nod/2 );
            nod /= 2;
            ok = 1;
        }
    }
}

void HeapDown( int nod )
{
    bool ok = 1;
    while ( ok )
    {
        ok = 0;
        if ( ( heap[nod] > heap[nod*2] ) && ( nod*2 <= nrheap ) )
        {
            if ( ( heap[nod*2] > heap[nod*2+1] )&& ( nod*2+1 <= nrheap ) )
            {
                HeapSwap( nod, nod*2+1 );
                nod = nod*2+1;
                ok = 1;
            }
            else
            {
                HeapSwap( nod, nod*2 );
                nod *= 2;
                ok = 1;
            }
        }
        else
        {
            if ( ( heap[nod] > heap[nod*2+1] )&& ( nod*2+1 <= nrheap ) )
            {
                HeapSwap( nod, nod*2+1 );
                nod = nod*2+1;
                ok = 1;
            }
        }
    }
}


void HeapAdd( int vpoz )
{
    ++active;

    heap[++nrheap] = cost1[vpoz];
    heaptov[nrheap] = vpoz;
    vtoheap[vpoz] = nrheap;

    HeapUp( nrheap );
}

void HeapRemoveFirst()
{
    int nod = 1;
    bool ok = 1;
    while ( ok )
    {
        ok = 0;

        if ( nod*2+1 > nrheap )
        {
            if ( nod*2 <= nrheap )
            {
                heap[nod] = heap[nod*2];
                vtoheap[heaptov[nod*2]] = nod;
                heaptov[nod] = heaptov[nod*2];

                nod *= 2;
                ok = 1;
            }
        }
        else
        {
            if ( heap[nod*2] < heap[nod*2+1] )
            {
                heap[nod] = heap[nod*2];
                vtoheap[heaptov[nod*2]] = nod;
                heaptov[nod] = heaptov[nod*2];

                nod *= 2;
                ok = 1;
            }
            else
            {
                heap[nod] = heap[nod*2+1];
                vtoheap[heaptov[nod*2+1]] = nod;
                heaptov[nod] = heaptov[nod*2+1];

                nod = nod*2+1;
                ok = 1;
            }
        }
    }

    --active;
}

void HeapUpdate( int nod )
{
    heap[nod] = cost1[heaptov[nod]];

    if ( heap[nod] < heap[nod/2] )
    {
        HeapUp( nod );
    }
    else
    {
        HeapDown( nod );
    }
}

int main()
{
    freopen( "dijkstra.in", "r", stdin );
    freopen( "dijkstra.out", "w", stdout );

    int nrm, nrnod, i;

    scanf( "%d %d\n", &nrnod, &nrm );


    int x, y, c;
    for ( i = 0; i < nrm; ++i )
    {
        scanf( "%d %d %d\n", &x, &y, &c );

        vec[x].push_back(y);
        cost[x].push_back(c);
        ++v[x];
    }

    heap[0] = -( 1<<30 );

    cost1[1] = 0;
    HeapAdd( 1 );

    int nod;

    while ( active > 0 )
    {
        nod = heaptov[1];
        for ( i = 0; i < v[nod]; ++i )
        {
            if ( vec[nod][i] == 5 )
            {
                int a = cost1[nod];
                a = 1;
            }


            if ( visited[vec[nod][i]] )
                continue;

            if ( !cost1[vec[nod][i]] )
            {
                cost1[vec[nod][i]] = cost1[nod] + cost[nod][i];
                HeapAdd( vec[nod][i] );

                continue;
            }

            if ( cost1[vec[nod][i]] > cost1[nod] + cost[nod][i] )
            {
                cost1[vec[nod][i]] = cost1[nod] + cost[nod][i];

                HeapUpdate( vtoheap[vec[nod][i]] );
            }
        }

        visited[heaptov[1]] = 1;
        HeapRemoveFirst();
    }

    for ( i = 2; i <= nrnod; ++i )
    {
        printf( "%d\n", cost1[i] );
    }


    fclose( stdin );
    fclose( stdout );

    return 0;
}