#include <bits/stdc++.h>

using namespace std;

const int MAXN = 50005;

#define y first
#define c second

vector<pair<int, int> > graf[MAXN];

int dist[MAXN], viz[MAXN];
queue<int>coada;

int main()
{
    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");
    int n, m;
    fin >> n >> m;
    for(int i = 1; i <= m; ++i){
        int inputx, inputy, inputc;
        fin >> inputx >> inputy >> inputc;
        graf[inputx].push_back({inputy, inputc});
    }
    for(int i = 2; i <= n; ++i) dist[i] = 1e9;
    bool ok = 1;
    coada.push(1);
    viz[1]++;
    while(!coada.empty() && ok){
        int nod = coada.front();
        coada.pop();
        for(auto edge : graf[nod]){
            if(dist[edge.y] > dist[nod] + edge.c){
                dist[edge.y] = dist[nod] + edge.c;
                coada.push(edge.y);
                viz[edge.y]++;
                if(viz[edge.y] == n) ok = 0;
            }
        }
    }
    if(ok) for(int i = 2; i <= n; ++i) fout << dist[i] << " ";
    else fout << "Ciclu negativ!";
    return 0;
}