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

using namespace std;

const int oo = 2000000000;

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

vector< pair<int,int> > G[50010];
queue<int> Q;
int i,n,m,x,y,c,cost[50010];

int main()
{
    f >> n >> m;
    for( i = 1 ; i <= m ; i++ )
    {
        f >> x >> y >> c;
        G[ x ].push_back( make_pair( y , c ) );
    }

    for( i = 1 ; i <= n ; i++ )
    {
        cost[ i ] = oo;
    }

    cost[ 1 ] = 0;
    Q.push( 1 );
    while( Q.size() )
    {
        x = Q.front();
        Q.pop();
        for( i = 0 ; i < G[ x ].size() ; i++ )
        {
            y = G[ x ][ i ].first;
            if( cost[ y ] > cost[ x ] + G[ x ][ i ].second )
            {
                cost[ y ] = cost[ x ] + G[ x ][ i ].second;
                Q.push( y );
            }
        }
    }

    for( i = 2 ; i <= n ; i++ )
    {
        if( cost[ i ] == oo )
            cost[ i ] = 0;
        g << cost[ i ] << ' ';
    }

    return 0;
}