#include<iostream>
#include<fstream>
#include<cstring>
using namespace std;

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];
    
    memset(d, 1, sizeof(d)); 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]=d[edge[i].a]+edge[i].c;
                                   t=true;
                                   }
                   }
           k++;
           }
     return(t);
     }