#include <iostream>
#include <fstream>
#include <vector>
#include <deque>

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
#define dim 50005
#define inf 1000000002
struct muchie
{
    int y,c;
};
vector<muchie> v[dim];
deque<int> dq;
int n,dist[dim],fr[dim];
void init()
{
    int i;
    for(i=1;i<=n;i++)
        dist[i]=inf;
}
bool bellman(int nod)
{
    int x,y,c;
    init();
    dist[nod]=0;
    dq.push_back(nod);
    while(!dq.empty())
    {
        x=dq.front();
        dq.pop_front();
        if(dist[x]!=inf)
        {
            for(auto z:v[x])
            {
                y=z.y;
                c=z.c;
                if(dist[y]>dist[x]+c)
                {
                    fr[y]++;
                    if(fr[y]==n)
                    {
                        return true;
                    }
                    dist[y]=dist[x]+c;
                    dq.push_back(y);
                }
            }
        }
    }
    return false;
}

int main()
{
    int m,i,x,y,c;
    bool rasp;
    fin>>n>>m;
    for(i=0;i<m;i++)
    {
        fin>>x>>y>>c;
        v[x].push_back({y,c});
    }
    rasp=bellman(1);
    if(rasp==true)
    {
        fout<<"Ciclu negativ!";
    }
    else
    {
        for(i=2;i<=n;i++)
        {
            fout<<dist[i]<<" ";
        }
    }
    return 0;
}