#include <bits/stdc++.h>
#define N 50005
#define inf 2e9
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n,m,d[N],contor[N];
vector<pair<int,int> >g[N];
bool viz[N],ok;
queue<int> q;
void BellmanFord()
{
    q.push(1);
    viz[1]=1;
    contor[1]=1;
    fill(d,d+n+1,inf);
    d[1]=0;
    while(!q.empty() && !ok)
    {
        int k=q.front();
        q.pop();
        viz[k]=0;
        for(auto x:g[k])
            if(!viz[x.first] && d[k]+x.second<d[x.first])
                if(contor[x.first]>n) ok=1;
                else contor[x.first]++,viz[x.first]=1,
                    d[x.first]=d[k]+x.second,q.push(x.first);
    }
}
int main()
{
    int i,x,y,cost;
    fin>>n>>m;
    while(m--)
    {
        fin>>x>>y>>cost;
        g[x].push_back({y,cost});
    }
    BellmanFord();
    if(!ok)
    for(int i=2;i<=n;i++)
        fout<<d[i]<<" ";
    else fout<<"Ciclu negativ!";
    return 0;
}