#include <fstream>
#include <vector>
#define INF 1000000*1000
using namespace std;
ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");
int i, j, n, m, nod, cost, vecin, x, y, c, st, dr;
int v[50002], iq[50002], d[50002];
vector <pair<int, int>> L[50002];
int a[50002];
int main() {
    cin>>n>>m;
    for(i=1;i<=m;i++){
        cin>>x>>y>>c;
        L[x].push_back({y, c});
    }
    for(i=1;i<=n;i++)
        d[i]=INF+2;
    st=1;
    dr=1;
    a[dr]=1;
    d[1]=0;
    v[1]=1;
    while(st<=dr){
        nod=a[st];
        v[nod]=0;
        st++;
        for(i=0;i<L[nod].size();i++){
            vecin=L[nod][i].first;
            cost=L[nod][i].second;
            if(d[vecin]>d[nod]+cost){
                d[vecin]=d[nod]+cost;
                if(v[vecin]==0){
                    iq[vecin]++;
                    if(iq[vecin]==n){
                        cout<<"Ciclu negativ!";
                        return 0;
                    }
                    dr++;
                    a[dr]=vecin;
                    v[vecin]=1;
                }
            }
        }
    }
    for(i=2;i<=n;i++)
        cout<<d[i]<<" ";


}