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

using namespace std;

#define IN "dijkstra.in"
#define OUT "dijkstra.out"
#define l 104*10
#define pb push_back

int x , y , v , n , p , m;
int cost[l];

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

void Read()
{
    int i;

    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 Solve()
{
    int i;

    cost[1] = 1;

    Q.push(1);

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

        for ( i = 0 ; i < G[x].size() ; i ++ )
            if ( cost[G[x][i]] == 0 or cost[G[x][i]] > cost[x] + C[x][i] )
        {
            cost[G[x][i]] = cost[x]+C[x][i];
            Q.push(G[x][i]);
        }

        Q.pop();
    }

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

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

    Read();
    Solve();
}