#include <fstream>
#include <vector>
#include <queue>
#define MAX 50000005

using namespace std;

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

vector< pair<int,int> > edges[50005] ;
queue< int > Q ;

int n , m , i , x , y , w , dist[50005] , u ;

int main()
{
    in >> n >> m ;

    for ( i = 1 ; i <= m ; i ++ )
    {
        in >> x >> y >> w ;
        edges[x].push_back(make_pair(y,w));
    }

    dist[1] = 0 ;
    Q.push(1);

    for ( i = 2 ; i <= n ; i ++ )
    {
       dist[i] = MAX ;
       Q.push(i);
    }

    while ( !Q.empty() )
    {
        x = Q.front();

        for ( i = 0 ; i < edges[x].size() ; i ++ )
        {
            if ( dist[edges[x][i].first] > dist[x] + edges[x][i].second )
            {
                dist[edges[x][i].first] = dist[x] + edges[x][i].second ;
                Q.push(edges[x][i].first);
            }
        }

        Q.pop();
    }

    for ( i = 2 ; i <= n ; i ++ )
    {
        if ( dist[i] != MAX )
        {
            out << dist[i] << " " ;
        }
        else
        {
            out << "0 " ;
        }
    }

    return 0;
}