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

using namespace std;

ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");

struct apa{
    int n,c;
}a;
int d[50000], viz[50000], fr[50000], n, m, x, ok;
vector<apa> v[50000];

int cost(int i,int j)
{
    for(auto a:v[i])
    {
        if(a.n==j)
            return a.c;
    }
}

void Belmand(int start)
{
    queue<int> q;
    q.push(start);
    while(!q.empty())
    {
        int j=q.front();
        viz[j]=0;
        q.pop();
        for(auto i: v[j])
        {
            if(d[i.n]>d[j]+cost(j,i.n))
            {
                d[i.n]=d[j]+cost(j,i.n);
                if(viz[i.n]==0)
                {
                    fr[i.n]++;
                    if(fr[i.n]>n)
                    {
                        ok=1;
                        return;
                    }
                    q.push(i.n);
                    viz[i.n]=1;
                }
            }
        }
    }
}

int main()
{
    cin>>n>>m;
    for(int i=2;i<=n;i++)
        d[i]=1e9;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>a.n>>a.c;
        v[x].push_back(a);
    }
    Belmand(1);
    if(ok==1)
    {
        cout<<"Ciclu negativ!";
        return 0;
    }
    for(int i=2;i<=n;i++)
        cout<<d[i]<<" ";
}