#include<fstream>
#include<vector>
#include<queue>
#define NMAX 50010
#define MMAX 250010
#define INF 200010000

using namespace std;

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

struct muchie
{
    int nod, cost, o;
};

vector<muchie> a[NMAX];

int n, m, d[NMAX], nr[MMAX], vz[NMAX];

queue<int> q;

void Citeste()
{
    int i, x, y;
    muchie r;

    f>>n>>m;

    for (i=1; i<=m; ++i)
    {
        f>>x>>r.nod>>r.cost;
        r.o=i;
        a[x].push_back(r);
    }
}

void Solve()
{
    int i, gata=0, nod;
    muchie r;

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

    d[1]=0; q.push(1); vz[1]=1;

    while (!q.empty() && !gata)
    {
        nod=q.front(); q.pop(); vz[nod]=0;

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

            if (d[r.nod]>d[nod]+r.cost)
            {
                d[r.nod]=d[nod]+r.cost;
                if (!vz[r.nod])
                {
                    q.push(r.nod);
                    vz[r.nod]=1;
                }
                ++nr[r.o];
                if (nr[r.o]==n-1)
                {
                    gata=1;
                    break;
                }
            }
        }
    }

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

int main()
{
    Citeste();

    Solve();

    f.close();
    g.close();

    return 0;
}