#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>

#define NMAX 50005
#define pb push_back
#define mp make_pair
#define nod first
#define cost second

using namespace std;

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

int N, M, H[NMAX], Poz[NMAX], D[NMAX], i, x, y, c, Nr, NodMin;
vector< pair< int, int > > G[NMAX];
vector< pair< int, int > >::iterator it;

inline void Swap( int a, int b )
{
    int aux = H[a];
    H[a] = H[b];
    H[b] = aux;

    Poz[ H[a] ] = a;
    Poz[ H[b] ] = b;
}

inline void HeapDown( int NOD )
{
    int FiuSt = NOD*2;
    if( FiuSt <= Nr )
    {
        int FiuDr = FiuSt + 1, Fiu = FiuSt;
        if( FiuDr <= Nr && D[ H[FiuDr] ] < D[ H[FiuSt] ] )
            Fiu = FiuDr;

        if( D[ H[Fiu] ] < D[ H[NOD] ] )
        {
            Swap( NOD, Fiu );
            HeapDown( Fiu );
        }
    }
}

inline void HeapUp( int NOD )
{
    if( NOD <= 1 ) return;

    int T = NOD/2;
    if( D[ H[T] ] > D[ H[NOD] ] )
    {
        Swap( T, NOD );
        HeapUp( T );
    }
}

inline void BuildHeap()
{
    for( int ii = 2 ; ii <= N; ii++ )
        HeapUp( ii );
}

inline void Scoate( int &minim )
{
    minim = H[1];
    Swap( 1, Nr-- );
    HeapDown( 1 );
}

int main()
{
    in >> N >> M;
    while( M-- )
    {
        in >> x >> y >> c;
        G[x].pb( mp( y, c ) );
    }

    memset( D, 0x3f3f, sizeof(D) );
    for( i = 1; i <= N; i++ )
        H[i] = Poz[i] = i;

    D[1] = 0;
    Nr = N;
    BuildHeap();

    while( Nr )
    {
        Scoate( NodMin );
        for( it = G[NodMin].begin(); it != G[NodMin].end(); it++ )
            if( D[ (*it).nod ] > D[NodMin] + (*it).cost )
            {
                D[ (*it).nod ] = D[NodMin] + (*it).cost;
                HeapDown( Poz[ (*it).nod ] );
            }
    }

    for( i = 2; i <= N; i++ )
        out << D[i] << ' ';
    out << '\n';

    return 0;
}