#include <bits/stdc++.h>
using namespace std;
ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");
int const lmax=50007;
int const vmax=1007;
queue <int> q;
int n,m;
vector <pair<int,int> >G[lmax];
int d[lmax],cnt[lmax];
bool viz[lmax],ok=true;
void BellmanFord(int nod)
{
    viz[nod]=true;
    cnt[nod]++;
    d[nod]=0;
    q.push(nod);
    while(q.empty()==false)
    {
        int best=q.front();
        q.pop();
        viz[best]=0;
        for(auto vec:G[best])
        {
            if(d[best]+vec.second<d[vec.first])
            {
                if(cnt[vec.first]>=n)
                {
                    ok=false;
                    return;
                }
                d[vec.first]=d[best]+vec.second;

                if(viz[vec.first]==false)
                {
                    viz[vec.first]=true;
                    cnt[vec.first]++;
                    q.push(vec.first);

                }
            }
        }
    }
}
int main()
{
    fin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        fin>>a>>b>>c;
        G[a].push_back({b,c});
    }
    for(int i=1;i<=n;i++)
    {
        d[i]=lmax*vmax;
    }
    BellmanFord(1);
    if(ok==false)
    {
        fout<<"Ciclu negativ!";
    }
    else
    {
        for(int i=2;i<=n;i++)
        {
            fout<<d[i]<<" ";
        }
    }
    fin.close();
    fout.close();
    return 0;
}