#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
#define INF 1000000

struct cell{
           int a,b,c;
           };

bool BellmanFord(cell edge[], int m, int n, int d[]);

int main(){
    ifstream cinr("bellmanford.in");
    ofstream cour("bellmanford.out");
    int n,m;
    cinr >> n >> m;
    cell edge[m];
    int d[n+1];
    for(int i=0; i<=n; i++) d[i]=INF; d[1]=0;
    
    for(int i=0; i<m; i++){
            cinr >> edge[i].a;
            cinr >> edge[i].b;
            cinr >> edge[i].c;
            }
    
    if(BellmanFord(edge,m,n,d)) cour << "Ciclu negativ!";
    else                        for(int i=2; i<=n; i++) cour << d[i] << " ";
    cinr.close(); cour.close();      
    }
   
bool BellmanFord(cell edge[], int m, int n, int d[]){
     bool t=true;
     int k=1;
     while(t && k<n){
           t=false;   
           for(int i=0; i<m; i++){
                   if(d[edge[i].b]>d[edge[i].a]+edge[i].c){
                                   d[edge[i].b]=max(-INF,d[edge[i].a]+edge[i].c);
                                   t=true;
                                   }
                   }
           k++;
           }
     return(t);
     }