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

using namespace std;

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

struct muchie
{
    int x, cost, ord;
};

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

vector<muchie> v[NMAX];
queue<int> q;

void read();
void bellman_ford();

int main()
{
    read();
    bellman_ford();
    fin.close();
    fout.close();
    return 0;
}

void read()
{
    int x, y, cost, i;
    muchie r;
    fin >> n >> m;
    for (i=1; i<=m; i++)
    {
        fin >> x >> y >> cost;
        r.cost=cost;
        r.ord=i;
        r.x=y;
        v[x].push_back(r);
    }
    for (i=1; i<=n; i++)
        cmin[i]=INF;
}

void bellman_ford()
{
    int i, changes=0, nod, val;
    muchie r;
    q.push(1);
    cmin[1]=0;
    while (!changes && !q.empty())
    {
        nod=q.front();
        q.pop();
        for (i=0; i<v[nod].size(); i++)
        {
            r=v[nod][i];
            val=cmin[nod]+r.cost;
            if (val<cmin[r.x])
            {
                cmin[r.x]=val;
                q.push(r.x);
                nr[r.ord]++;
                if (nr[r.ord]==n)
                {
                    changes=1;
                    break;
                }
            }
        }
    }
    if (changes)
        fout << "Ciclu negativ!";
    else
        for (i=2; i<=n; i++)
            fout << cmin[i] << " ";
}