#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream cin ("bellmanford.in");
ofstream cout ("bellmanford.out");
#define INF 250000*1000
using namespace std;
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];
queue <int> a;
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;
    a.push(1);
    d[1]=0;
    v[1]=1;
    while(!a.empty()){
        nod=a.front();
        v[nod]=0;
        a.pop();
        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;
                    }
                    a.push(vecin);
                    v[vecin]=1;
                }
            }
        }
    }
    for(i=2;i<=n;i++)
        cout<<d[i]<<" ";


}