#include <bits/stdc++.h>
#define DIM 100005
#define INF 1000005
using namespace std;

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

int n, m, x, y, c;
vector< pair<int, int> > L[DIM];

int d[DIM], folosit[DIM];
bool v[DIM], modificat;
queue<int> coada;
int nod;

int main()
{
    in>>n>>m;
    for( int i = 1; i <= m; i++ )
    {
        in>>x>>y>>c;
        L[x].push_back( make_pair(y, c) );
    }

    d[1] = 0;
    coada.push(1);
    v[1] = true;

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

    while( !coada.empty() )
    {
        nod = coada.front();
        coada.pop();
        v[nod] = false;

        for( pair<int, int> vecin : L[nod] )
            if( d[vecin.first] > d[nod] + vecin.second )
            {
                d[vecin.first] = d[nod] + vecin.second;

                if( v[vecin.first] == false )
                {
                    coada.push( vecin.first );
                    v[vecin.first] = true;

                    folosit[vecin.first]++;
                    if( folosit[vecin.first] == n )
                    {
                        out<<"Ciclu negativ!";
                        return 0;
                    }
                }
            }

    }

    for( int i = 2; i <= n; i++ )
        out<<d[i]<<" ";

    return 0;
}