#include <fstream>
#include <vector>
#define MX 50001
using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n,m;
int d[MX];

struct vecin
{
    int y,c;
};
vector<vecin> v[MX];

void citire()
{
    int i,x;
    vecin e;
    fin>>n>>m;
    for(i=1; i<=m; i++)
    {
        fin>>x>>e.y>>e.c;;
        v[x].push_back(e);
    }

    for(i=2; i<=n; i++)
    {
        d[i] = (1<<30);
    }
}

int main()
{
    int i,j,ok=1;
    vector<vecin>::iterator it;
    citire();

    for(i=1; i<n; i++)
    {
        //Aici incepe distractia
        for(j=1; j<=n; j++)
        {
            for(it=v[j].begin(); it!=v[j].end(); it++)
            {
                if(d[j] + it->c < d[it->y])
                {
                    d[it->y] = d[j] + it->c;
                }
            }
        }
    }

    for(j=1; j<=n; j++)
    {
        for(it=v[j].begin(); it!=v[j].end(); it++)
        {
            if(d[j] + it->c < d[it->y])
            {
                ok = 0;
            }
        }
    }

    if(ok == 0)
    {
        fout<<"Ciclu negativ!";
    }
    else
    {
        for(i=2; i<=n; i++)
        {
            fout<<d[i]<<' ';
        }
    }

    fin.close(); fout.close();
    return 0;
}