#include <bits/stdc++.h>
#define NMAX 50005
#define inf 1e9

using namespace std;

FILE*f=fopen("bellmanford.in","r");
FILE*g=fopen("bellmanford.out","w");

vector<pair<int,int> > v[NMAX];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > h;
int n,m,d[NMAX],viz[NMAX],x,y,z,s,nod;

int main() {
    int i;
    s=1;
    fscanf(f,"%d%d",&n,&m);
    for (i=1;i<=m;i++) {
        fscanf(f,"%d%d%d",&x,&y,&z);
        v[x].push_back(make_pair(z,y));
    }
    for (i=1;i<=n;i++)
        d[i]=inf;
    d[s]=0;
    h.push(make_pair(0,1));
    while (!h.empty()) {
        nod=h.top().second;
        h.pop();
        if (viz[nod]<n) {
            for (i=0;i<v[nod].size();i++)
                if (v[nod][i].first+d[nod]<d[v[nod][i].second]) {
                    d[v[nod][i].second]=v[nod][i].first+d[nod];
                    h.push(make_pair(d[v[nod][i].second],v[nod][i].second));
                }
        }
        else {
            fprintf(g,"Ciclu negativ!");
            return 0;
        }
        viz[nod]++;
    }
    for (i=1;i<=n;i++)
        if (i!=s)
            if (d[i]==inf) fprintf(g,"0 ");
            else fprintf(g,"%d ",d[i]);
    return 0;
}