#include <cstdio>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

#define IN "dijkstra.in"
#define OUT "dijkstra.out"
#define l 50003
#define pb push_back

int d[l],sol[l];
bool fr[l];

vector<int>G[l];
vector<int>C[l];
queue<int>Q;

int k , n , m;

void Read()
{
    int i , v , x , y;
    scanf ( "%d%d" , &n , &m );

    for ( i = 1 ; i <= m ; i ++ ){
            scanf ( "%d%d%d" , &x , &y , &v );
            G[x].pb(y),C[x].pb(v);
    }
}

void Init()
{
    int i;

    for ( i = 2 ; i <= l ; i ++ )
        d[i] = INT_MAX;
}

void Precalc()
{
    int i , x;
    sol[k=1] = 1;
    for ( i = 0 ; i < G[1].size() ; i ++ )
        Q.push(G[1][i]) , sol[++k] = G[1][i];

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

        for ( i = 0 ; i < G[x].size() ; i ++ )
            if ( fr[G[x][i]] == 0 )
                sol[++k] = G[x][i] , Q.push(G[x][i]) , fr[G[x][i]] = 1;

       // Q.pop();
    }

}

void Solve()
{
    Init();
    int i , j , z;

    for ( i = 1 ; i <= k ; i ++ ){
        for ( j = 0 ; j < G[sol[i]].size() ; j ++ )
            {
                if ( d[sol[i]]+C[sol[i]][j] < d[G[sol[i]][j]] )
                    d[G[sol[i]]
                    [j]] = d[sol[i]]+C[sol[i]][j];
            }


}

    for ( i = 2 ; i <= n ; i ++ )
        if ( d[i] != INT_MAX )
        printf ( "%d " , d[i] );
        else printf ("0 ");
}

int main()
{
    freopen ( IN , "r" , stdin );
    freopen ( OUT , "w" , stdout );

    Read();
    Precalc();
    Solve();
}