#include <bits/stdc++.h>

using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n,m,x,y,c,step;
int mn[50005];
int changed[50005];
vector<pair<int,int> >nod[50005];
queue<int>q;
bool verify()
{
    int hm=q.size();
    if(hm==0)return false;
    for(int i=1;i<=hm;i++)
    {
        int pos=q.front();
        q.pop();
        for(int j=0;j<nod[pos].size();j++)
        {
            if(mn[nod[pos][j].first]<=mn[pos]+nod[pos][j].second)continue;
            mn[nod[pos][j].first]=mn[pos]+nod[pos][j].second;
            if(changed[nod[pos][j].first]==step)continue;
            changed[nod[pos][j].first]=step;
            q.push(nod[pos][j].first);
        }
    }
    return true;
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        nod[x].push_back({y,c});
    }
    for(int i=2;i<=n;i++)
        mn[i]=INT_MAX;
    q.push(1);
    step=1;
    while(verify() && step<=n+1)
        step++;
    if(step==n+2)
    {
        fout<<"Ciclu negativ!";
        return 0;
    }
    for(int i=2;i<=n;i++)
        fout<<mn[i]<<" ";
    return 0;
}