#include <fstream>
#include <vector>
#define INF 2000000000
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n, m, x, y, dist;
vector< pair<int, int> > g[50010];
bool viz[50010];
int p,u;
int coada[1000010];
int decateori[50010];
int d[50010];

bool BellmanFord()
{
    while(p<=u)
    {
        viz[coada[p]]=0;

        for(int i=0; i<g[coada[p]].size(); i++)
            if(d[coada[p]]+g[coada[p]][i].second<d[g[coada[p]][i].first])
        {
            d[g[coada[p]][i].first]=d[coada[p]]+g[coada[p]][i].second;

            if(!viz[g[coada[p]][i].first])
            {
                viz[g[coada[p]][i].first]=1;
                coada[++u]=g[coada[p]][i].first;
                decateori[g[coada[p]][i].first]++;

                if(decateori[g[coada[p]][i].first]==n-1)
                {
                    return 1;
                }
            }
        }
        p++;
    }

    return 0;
}

int main()
{
    fin>>n>>m;

    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>dist;
        g[x].push_back(make_pair(y, dist));
        //g[y].push_back(make_pair(x, dist));
    }

    for(int i=2;i<=n;i++)
        d[i]=INF;

    p=u=1;
    coada[1]=1;
    decateori[1]=1;
    viz[1]=1;

    if(BellmanFord())
        fout<<"Ciclu negativ!";
    else
        for(int i=2;i<=n;i++)
            fout<<d[i]<<' ';

    return 0;
}