#include <iostream>
#include <fstream>

using namespace std;

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

const int N = 50005;
const int M = 250005;
const int INF = (1<<31) - 1;

int n,m,nr,cst[M],vf[M],lst[M],urm[M],nrq[N],q[N+1],d[N];
int st,dr;
bool inq[N];

void Adauga(int x,int y, int c)
{
   vf[++nr] = y;
   cst[nr] = c;
   urm[nr] = lst[x];
   lst[x] = nr;
}

void inc(int &x)
{
   x++;
   if (x == N+1)
   {
       x = 0;
   }
}

bool bf(int nod)
{
    int x,y,c;
    for (int i=1; i<=n; i++)
    {
        d[i] = INF;
    }
    d[nod] = 0;
    st = 0;
    dr = -1;
    inc(dr);
    q[dr] = nod;
    inq[nod] = 1;
    nrq[nod]++;
    while (dr != st-1)
    {
        x = q[st];
        inc(st);
        inq[x] = 0;
        for (int p=lst[x]; p != 0; p = urm[p])
        {
            y = vf[p];
            c = cst[p];
            if (d[x] + c < d[y])
            {
                d[y] = d[x] + c;
                if (!inq[y])
                {
                    inc(dr);
                    q[dr] = y;
                    inq[y] = 1;
                    nrq[y]++;
                    if (nrq[y] == n)
                    {
                        return 0;
                    }
                }
            }
        }
    }
    return 1;
}

int main()
{
    in >> n >> m;
    for (int i=1,x,y,c; i<=m; i++)
    {
        in >> x >> y >> c;
        Adauga(x,y,c);
    }
    int ok = bf(1);
    if (ok == 0)
    {
        out << "Ciclu negativ!";
    }
    else
    {
        for (int i=2; i<=n; i++)
        {
            out << d[i] << " ";
        }
    }
    return 0;
}