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

using namespace std;

#define IN "dijkstra.in"
#define OUT "dijkstra.out"
#define pb push_back
#define inf 250000*1200
#define mk make_pair

int d[50004];
int n , m;
vector<int>G[50004];
vector<int>C[50004];

int Plus(int a)
{
    return -a;
}

void Fill()
{
    int i;

    for ( i = 2 ; i <= n ; i ++ )
        d[i] = inf;
}

priority_queue < pair < int,int > >Q;
void Read()
{
    int x , y , c , i;

    scanf ( "%d%d" , &n , &m );

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

void Dijkstra()
{
    int i , nod , cost , x , y;

    Fill();

    Q.push(mk(0,1));
    d[0] = -1;

    while (!Q.empty())
    {
        nod = Q.top().second;
        cost = Plus(Q.top().first);


        for ( i = 0 ; i < G[nod].size() ; i ++ )
        {
            x = G[nod][i];
            y = C[nod][i];

            if ( d[x] > d[nod]+y )
                d[x] = d[nod]+y , Q.push(mk(-d[x],x));
        }

        Q.pop();

    }

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

}

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

    Read();
    Dijkstra();
}