#include <stdio.h>
 
#define MAX_N 5001
#define MAX_M 25001
#define INF 100000
 
struct edge
{
    int a, b, c;
} e[MAX_M];
 
int N, M, i, j, k, cost[MAX_N];
 
 
void solve()
{
    int i, j;
    cost[1] = 0;
    
    for( i = 2 ; i <= N; i++) {

        cost[i] = INF;
    }

    for( i = 1 ; i <= N; i++ ) {
        for( j = 1; j <= M; j++) {

            if( cost[e[j].a] + e[j].c < cost[e[j].b] ) {
                
                cost[e[j].b] = cost[e[j].a] + e[j].c;
            }
        }
    }
}   
 
int check_negativ()
{
    int i;
    for( i = 1; i <= M; i++ ) {
        
        if( cost[e[i].a] + e[i].c < cost[e[i].b] ) {
            return 1;
        }
    }
    return 0;
}         
 
int main(int argc, char *argv[])
{
    if ( argc < 3 ) {
        fprintf(stderr, "USAGE: ./bellman_ford FILE_IN FILE_OUT\n");
        return -1;
    }


    FILE *f_in = fopen ( argv[1], "r" );
    FILE *f_out = fopen ( argv[2], "w" );
 
    if ( !f_in ) {
        perror ( "can't open file!");
        return -1;
    }

    fscanf(f_in, "%d %d", &N, &M);
    for( i = 1; i <= M; i++ ) {

        fscanf(f_in, "%d %d %d", &e[i].a, &e[i].b, &e[i].c);
    }
    solve();
    
    if( check_negativ() ) {
        printf("Ciclu negativ!\n");
        return 0;
    }

    for( i = 2; i <= N; i++ ) {
        fprintf(f_out, "%d ", cost[i]);
    }
    fprintf(f_out, "\n");

    fclose(f_out);
    fclose(f_in);

    return 0;
}