#include<fstream>
#include<queue>
#include<utility>
#define NMAX 50010
#define INF 250000010
#define f first
#define s second

using namespace std;

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

vector<pair<int, int> > a[NMAX];
queue<int> q;
int n, m, vz[NMAX], vzq[NMAX], D[NMAX];

void Citeste()
{
    int x, y, c;

    f>>n>>m;
    while (m--)
    {
        f>>x>>y>>c;
        a[x].push_back(make_pair(c, y));
    }
}

void Solve()
{
    int i, nod, ciclun=0;
    pair<int, int> r;

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

    q.push(1); D[1]=0; vzq[1]=1;
    while (!q.empty() && !ciclun)
    {
        nod=q.front(); q.pop(); vzq[nod]=0;

        for (i=0; i<a[nod].size(); ++i)
        {
            r=a[nod][i];

            if (r.f+D[nod]<D[r.s])
            {
                D[r.s]=r.f+D[nod];
                ++vz[r.s];
                if (vz[r.s]==n) ciclun=1;
                if (!vzq[r.s])
                {
                    q.push(r.s);
                    vzq[r.s]=1;
                }
            }
        }
    }

    if (ciclun) g<<"Ciclu negativ!";
    else
        for (i=2; i<=n; ++i) g<<D[i]<<" ";
}

int main()
{
    Citeste();

    Solve();

    f.close();
    g.close();
    return 0;
}