#include <cstdio>
#include <vector>
#include <deque>
#define INF ((1LL<<31)-1)
#define DIM 51000
using namespace std;
 
int N, M, K, X, Y, Z;
int D[DIM], F[DIM], Nr[DIM];
vector <int> V[DIM];
deque <int> C;
 
int main(){
 
    freopen("bellmanford.in" ,"r", stdin );
    freopen("bellmanford.out","w", stdout);
 
    scanf("%d %d", &N, &M);
 
    for(int i = 1; i <= M; i ++){
 
        scanf("%d %d %d", &X, &Y, &Z);
 
        V[X].push_back(Y);
        V[X].push_back(Z);
    }
 
    C.push_back(1);
    F[1] = 1;
    Nr[1] = 1;
 
    for(int i = 2; i <= N; i ++)
        D[i] = INF;
 
    while(!C.empty()){
         
        int nod = C.front();
 
        for(int i = 0; i < V[nod].size(); i += 2){
 
            int vec = V[nod][i+0];
            int cost= V[nod][i+1];
 
            if(D[vec] > D[nod] + cost){
 
                D[vec] = D[nod] + cost;
 
                if(F[vec] == 0){
 
                    Nr[vec] ++;
                    F[vec] = 1;
                    C.push_back(vec);
 
                    if(Nr[vec] == N){
                        
                       printf("Ciclu negativ!");
                       return 0;
                     }
                }
            }
        }
 
        F[nod] = 0;
        C.pop_front();
 
    }
 
    for(int i = 2; i <= N; i ++)
        printf("%d ", D[i]);
 
    return 0;
}