#include <fstream>
#include <vector>
#include <queue>
#define INF 10005
#define NMAX 50005

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

struct mch
    {
    int vf, c;
    };

vector <mch> a[50005];
queue <int> q;

int n, m, k;
int dmin[NMAX], nr[NMAX];

void citire();
bool Bellman_Ford();
void afisare();

int main()
{
    citire();
    afisare();

    return 0;
}

void citire()
{
    int i, x;
    mch muchie;
    muchie.vf=muchie.c=0;

    fin>>n>>m;

    for (i=1; i<=n+1; i++)
        {
        a[i].push_back(muchie);
        dmin[i]=INF;
        }
    dmin[1]=0;
    for (i=1; i<=m; i++)
        {
        fin>>x>>muchie.vf>>muchie.c;
        a[x].push_back(muchie); a[x][0].c++;
        }
    q.push(1);
}

bool Bellman_Ford()
{
    int i, x;
    bool negativ=false;

    while (!q.empty() && !negativ)
        {
        x=q.front(); q.pop();

        for (i=1; i<=a[x][0].c; i++)
            if (dmin[a[x][i].vf]>dmin[x]+a[x][i].c)
                {
                dmin[a[x][i].vf]=dmin[x]+a[x][i].c;
                nr[a[x][i].vf]++;

                if(nr[a[x][i].vf]==n)
                    {
                    negativ=true; break;
                    }
                q.push(a[x][i].vf);
                }
    }

    return negativ;
}

void afisare()
{   int i;
    if(Bellman_Ford())
        fout<<"Ciclu negativ!"<<'\n';
        else
        {
        for(i=2; i<=n; i++)
            fout<<dmin[i]<<' ';
        fout<<'\n';
        }
}