#include <bits/stdc++.h>
#define nmax 50005
#define mmax 250005
#define oo 1e9

using namespace std;

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

vector <pair<int, int>> graph[nmax];
int f[nmax], minimum_Distance[nmax];
int n, m;

queue <int> road;

bool bellmanFord()
{
    for ( int i = 2; i <= n; ++i )
        minimum_Distance[i] = oo;

    road.push(1);

    while ( road.size() )
    {
        int node = road.front();
        f[node]++;
        road.pop();

        if ( f[node] >= n )
            return false;

        for ( auto x:graph[node] )
        {
            if ( minimum_Distance[x.first] > minimum_Distance[node]+x.second )
            {
                minimum_Distance[x.first] = minimum_Distance[node]+x.second;
                road.push(x.first);
            }
        }
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    fin.tie(0); fout.tie(0);
    fin>>n>>m;

    for ( int i = 1; i <= m; ++i )
    {
        int first_Node, second_Node, cost;
        fin>>first_Node>>second_Node>>cost;
        graph[first_Node].push_back({second_Node, cost});
    }

    if ( bellmanFord() == true )
        for ( int i = 2; i <= n; ++i )
            fout<<minimum_Distance[i]<<" ";
    else
        fout<<"Ciclu negativ!";
}