#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");

vector < pair<int,int> > l[50010];
int x,y,n,m,i,c,f[50010],d[50010],ok;
queue <int>q;

void bfs(){
    int fr,sc;
    q.push(1);
    while (q.size()) {
        x=q.front();
        f[x]++;
        if (f[x]==n){
            fout<<"Ciclu negativ!\n";
            return;
        }
        for (int i=0;i<l[x].size();i++) {
            fr=l[x][i].first,sc=l[x][i].second;
            if (d[x]+sc<d[fr]){
                d[fr]=d[x]+sc;
                q.push(fr);
            }
        }
        q.pop();
    }
    ok=1;
}

int main () {

    fin>>n>>m;
    while (m--) {
        fin>>x>>y>>c;
        l[x].push_back(make_pair(y,c));
    }
    for (i=2;i<=n;i++)
        d[i]=50000000;
    bfs();
    if (ok)
        for (i=2;i<=n;i++)
            fout<<d[i]<<" ";

    return 0;
}