#include <bits/stdc++.h>
using namespace std;
ifstream fin("bellmanford.in");
#define cin fin
ofstream fout("bellmanford.out");
#define cout fout
deque <int> dq;
vector <pair<int, int> > l[50010];
vector <int> r, cnt;
bitset <50010> id;
int n, m, x, y, c, cv, vc;
void citire(){
    cin>>n>>m;
    for(int i=0; i<m; i++){
        cin>>x>>y>>c;
        l[x].push_back({y, c});
    }
}
void init(int nod){
    cnt.resize(n+2);
    r.resize(n+2, 10100000);
    r[nod]=0;
}
bool bf(int nod){
    dq.push_back(nod);
    while(!dq.empty()){
        nod=dq.front();
        dq.pop_front();
        id[nod]=0;
        for(int i=0; i<l[nod].size(); i++){
            vc=l[nod][i].first;
            cv=l[nod][i].second;
            if(r[vc]>r[nod]+cv){
                r[vc]=r[nod]+cv;
                if(!id[vc]){
                    id[vc]=1;
                    dq.push_back(vc);
                    cnt[vc]++;
                    if(cnt[vc]>n){
                        cout<<"Ciclu negativ!";
                        return 0;
                    }
                }
            }
        }
    }
    return 1;
}
void afis(){
    for(int i=2; i<=n; i++){
        cout<<r[i]<<' ';
    }
}
int main(){
    citire();
    init(1);
    if(bf(1)) afis();
    return 0;
}