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

struct reb {
       int a,b,c;
       };
       
int main(){
    ifstream cinr ("bellmanford.in");
    ofstream cour ("bellmanford.out");
    int n,m,t=1;
    cinr >> n;
    cinr >> m;
    reb g[m];
    for(int i=0; i<=m-1; i++){
            cinr >> g[i].a;
            cinr >> g[i].b;
            cinr >> g[i].c;
            }
    int d[n+1], p[n+1];
    d[1]=0; p[1]=0;
    for(int i=2; i<=n; i++){
            p[i]=-1;
            d[i]=2000;
            }
for(int j=1; j<=n-2; j++){ 
    for(int i=0; i<=m-1; i++){
            if(d[g[i].b]>d[g[i].a]+g[i].c){
                                           d[g[i].b]=d[g[i].a]+g[i].c;
                                           p[g[i].b]=g[i].a;
                                           }
            }
}
    for(int i=0; i<=m-2; i++){
            if(d[g[i].b]>d[g[i].a]+g[i].c){ t=0; break; }
            }
    if(t){
          for(int i=2; i<=n; i++){
                  cour << d[i] << " ";
                  }
          }
    else {
         cour << "Ciclu negativ!"; 
         }
    //cin.ignore(2);
    
    return 0;
    }