#include <fstream>
#include <vector>
#include <limits>

using namespace std;

struct edge{
    int x, y, c;
};

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
const int INF = std::numeric_limits<int>::max();
int n, m, d[50001], ok = 1;
vector<edge> edges;

int main(){ 
    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        int x, y, c;
        fin >> x >> y >> c;
        edges.push_back({x, y, c});
    }
    for(int i = 1; i <= n; i++) d[i] = INF;
    d[1] = 0;
    for(int i = 1; i < n; i++) for(auto e : edges) if(d[e.y] > d[e.x] + e.c) d[e.y] = d[e.x] + e.c;
    for(auto e : edges) if(d[e.y] > d[e.x] + e.c) {ok = 0; break;}
    if(ok)
        for(int i = 2; i <= n; i++) fout << d[i] << ' ';
    else
        fout << "Ciclu negativ!";
    fin.close();
    fout.close();
    return 0;
}