#include <fstream>
#include <queue>
#define inf 10000000
using namespace std;

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

int n , node_start , cost[5005][5005] , vis[5005]  , dist[5005]  , father[5005] , m ;

void set_cost()
{
    for ( int i = 1 ; i <= n ; i++ )
        for ( int j = i + 1 ; j <= n ; j++ )
            cost[i][j] = cost[j][i] = inf ;
}

void prepare()
{
    for ( int i = 1 ; i <= n ; i++ )
    {
        dist[i] = cost[node_start][i] ;
        father[i] = node_start ;
    }
    vis[node_start] = 1 ;
    father[node_start] = 0 ;
}

void read()
{
    fin >> n >> m ;
    node_start = 1 ;
    set_cost() ;
    for ( int i = 1 ; i <= m ; i++ )
    {
        int x , y , z ;
        fin >> x >> y >> z ;
        cost[x][y] = z ;
    }
    prepare() ;
}

void solve()
{
    int dmin , vfmin ;
    for ( int j = 1 ; j <= n ; j++ )
    {
        dmin = inf ;
        for ( int i = 1 ; i <= n ; i++ )
            if ( !vis[i] && dmin > dist[i] )
            {
                dmin = dist[i] ;
                vfmin = i ;
            }
        vis[vfmin] = 1 ;
        for (
            int i = 1 ; i <= n ; i++ )
            if ( !vis[i] && dist[i] > dmin + cost[vfmin][i] )
            {
                father[i] = vfmin ;
                dist[i] = dmin + cost[vfmin][i] ;
            }
    }
}

void print()
{
    for ( int i = 2 ; i <= n ; i++ )
        if ( dist[i] == inf )
            fout << "0" << ' ' ;
        else
            fout << dist[i] << ' ' ;
}

int main()
{
    read() ;
    solve() ;
    print() ;
    return 0;
}