#include <bits/stdc++.h>
#define NMAX 50001
#define oo 1e9

using namespace std;

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

vector < tuple < int, int, int > > muchie;
int n, m, dist[NMAX];

void citire()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int x, y, c; fin>>x>>y>>c;
        muchie.push_back( make_tuple(x, y, c) );
    }
}
void bellman(int nod)
{
    for(int i=1; i<=n; i++)
        dist[i] = oo;
    dist[nod] = 0;

    int ok;
    for(int i=1; i<=n; i++)
    {
        ok = 0;
        for(auto a:muchie)
        {
            int x, y, c;
            tie(x, y, c) = a;

            if(dist[y] > dist[x] + c)
            {
                dist[y] = dist[x] + c;
                ok = 1;
            }
        }
    }
    if(ok == 1)
        fout<<"Ciclu negativ!";
    else
        for(int i=2; i<=n; i++)
            fout<<dist[i]<<' ';

}

int main()
{
    citire();
    bellman(1);

    return 0;
}