#include <iostream>
#include<fstream>
#include<vector>
#include<set>
#include<algorithm>

using namespace std;
vector<pair<long, long> >h;
vector<pair<long, long> >v[50001];
const int maxm=1e9;
struct ura{
long n1, n2, co;}inf[250001];

long t[50001], gat[50001];
int main() {
    long n, m, i, x, y, c, nod, cost, newn, ok, j;

    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");
    fin>>n>>m;
    ok=1;
    for(i=1; i<=m; i++) {
        fin>>inf[i].n1>>inf[i].n2>>inf[i].co;
        x=inf[i].n1;
        y=inf[i].n2;
        c=inf[i].co;
        v[x].push_back(make_pair(c, y));
    }
    t[1]=0;
    for(i=2; i<=n; i++) {
        t[i]=maxm;
    }
    h.push_back(make_pair(0, 1));
    make_heap(h.begin(), h.end());
    long long pas=0;
    while(h.size() && pas<=1LL*n*m) {
        pas++;
        pop_heap(h.begin(), h.end());
        nod=h.back().second;
        h.pop_back();
        gat[nod]=0;
        for(j=0; j<v[nod].size(); j++) {
            newn=v[nod][j].second;
            cost=v[nod][j].first;
            if(t[newn]>t[nod]+cost) {
                t[newn]=t[nod]+cost;
                if(gat[newn]==0) {
                    gat[newn]=0;
                    h.push_back(make_pair(-t[newn], newn));
                    push_heap(h.begin(), h.end());
                }
            }
        }
    }
    for(i=1;i<=m;i++) {
            if(t[inf[i].n1]+inf[i].co<t[inf[i].n2]) {
                    ok=0;
            }
    }
   if(ok==0) {
        fout<<"Ciclu negativ!\n";
   }
   else {
       for(i=2;i<=n;i++) {
            fout<<t[i]<<" ";
       }
   }
        return 0;
}