#include <iostream>
#include <fstream>
#include <vector>

#define INF 0x3F3F3F3F

using namespace std;

struct muchie{
    int start;
    int cost;
    int dest;
};

int n, m;

muchie muchii[250000];

int dist[50001];

bool bellmanford(int start){
    for(int i=1; i<=n; i++){
        dist[i]=INF;
    }
    dist[start]=0;

    for(int i=0; i<n-1; i++){
        for(int j=0; j<m; j++){
            muchie m=muchii[j];

            if(dist[m.start]+m.cost<dist[m.dest]){
                dist[m.dest]=dist[m.start]+m.cost;
            }
        }
    }

    for(int i=0; i<n-1; i++){
        for(int j=0; j<m; j++){
            muchie m=muchii[j];

            if(dist[m.start]+m.cost<dist[m.dest]){
                return false;
            }
        }
    }

    return true;
}

int main(){
    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");

    fin>>n>>m;

    int k=0;
    for(int i=0; i<m; i++){
        int x, y, c; fin>>x>>y>>c;

        muchii[k++]={x, c, y};
    }

    if(bellmanford(1)){
        for(int i=2; i<=n; i++){
            fout<<dist[i]<<" ";
        }
    }else{
        fout<<"Ciclu negativ!";
    }

    return 0;
}