#include<stdio.h>
#include<string.h>
#include<vector>
#include<queue>

using namespace std;

#define maxn 50001

vector <int> vec[maxn];
vector <int> cost[maxn];

queue <int> coada;
int dist[maxn], sel[maxn], last[ maxn ];

int bellman( int n){
  
    coada.push(1);
    memset(dist, 100, sizeof(dist));
    dist[1] = 0;
    while( coada.size() ) {
      
        int cine = coada.front();
        int cost_act = dist[cine];
        coada.pop();
        sel[ cine ]++;
        if( sel[ cine ] > n ) return 0;
        int nr_vec = vec[cine].size();
        for( int i = 0; i < nr_vec; ++i) {
            int vecin = vec[cine][i];
            if( cost_act + cost[cine][i] < dist[vecin] ) 
                dist[vecin] = cost_act + cost[cine][i];
                coada.push( vecin);
        }
    }
    return 1;
}

int main() {
    
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    int N, M;
    scanf("%d %d", &N, &M);
    
    for( int i = 1; i <= M; ++i){
         int a, b, c;
         scanf("%d %d %d", &a, &b, &c);
         vec[a].push_back(b);
         cost[a].push_back(c);
    }
    
    if(!bellman(N) )
        printf("Ciclu negativ!\n");
    else 
        for( int i = 2; i <= N; ++i) {
            if( dist[ i ] >= 50000000)
                dist[i] = 0;
            printf("%d ", dist[i]);
        }
    
    return 0;
}