#include <fstream>
#include <climits>
#include <vector>
#include <deque>
#define dim 50010
using namespace std;
vector <pair <int,int> > a[dim];
deque <int> c;
int f[dim];
int d[dim];
int fr[dim];
int i,n,m,nod,vecin,cost,x,y;

int main() {
    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");
    fin>>n>>m;
    for (i=1;i<=m;i++) {
        fin>>x>>y>>cost;
        a[x].push_back({y,cost});
    }
    for (i=1;i<=n;i++) {
        d[i]=INT_MAX;
    }
    d[1]=0;
    f[1]=1;
    c.push_back(1);
    while (!c.empty()) {
        nod=c.front();
        for (i=0;i<a[nod].size();i++) {
            vecin=a[nod][i].first;
            cost=a[nod][i].second;
            if (d[vecin]>d[nod]+cost) {
                d[vecin]=d[nod]+cost;
                if (f[vecin]==0) {
                    fr[vecin]++;
                    f[vecin]=1;
                    c.push_back(vecin);
                    if (fr[vecin]==n) {
                        fout<<"Ciclu negativ!";
                        return 0;
                    }
                }
            }
        }
        f[nod]=0;
        c.pop_front();
    }
    for (i=2;i<=n;i++) {
        fout<<d[i]<<" ";
    }
    return 0;
}