#include <fstream>
#include <vector>
#include <queue>

#define cost first
#define nod second

using namespace std;
int n,m,i,j,c,fv[100005];

vector < pair < int, int > >v[50005];
priority_queue < pair < int, int >, vector < pair < int, int > >, greater < pair < int, int > > > pq;
pair < int, int > aux;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int main()
{
    fin>>n>>m;
    for( int k = 1; k <= m; k++ )
    {
        fin>>i>>j>>c;
        v[ i ].push_back( { c, j } );
    }

    pq.push( { 0, 1 } );
    while( !pq.empty( ) )
    {
        aux = pq.top( );
        pq.pop( );
        if( fv[ aux.nod ] )
            continue;
        fv[ aux.nod ] = aux.cost;
        for( i = 0; i < v[ aux.nod ].size( ); i++ )
        {
            pq.push( { aux.cost + v[ aux.nod ][ i ].cost, v[ aux.nod ][ i ].nod } );
        }
    }
    for( i = 2; i <= n; i++ )
        fout<<fv[ i ]<<" ";
    return 0;
}