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

using namespace std;

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

struct structura
{
    int nod, cost;
};

vector <structura> graf[nmax];
int viz[nmax], dist[nmax];
int n, m;

bool bellmanFord()
{
    queue <int> Q;
    for ( int i = 2; i <= n; ++i )
        dist[i] = oo;
    Q.push(1);
    while ( Q.size() )
    {
        int nod = Q.front();
        Q.pop();
        viz[nod]++;
        if ( viz[nod] >= n  )
            return false;
        for ( auto x:graf[nod] )
            if ( dist[x.nod] > dist[nod]+x.cost )
            {
                dist[x.nod] = dist[nod]+x.cost;
                Q.push(x.nod);
            }
    }
    return true;
}

int main()
{
    fin>>n>>m;
    for ( int i = 1; i <= m; ++i )
    {
        int a, b, cost;
        fin>>a>>b>>cost;
        graf[a].push_back({b, cost});
    }
    if ( bellmanFord() )
        for ( int i = 2; i <= n; ++i )
            fout<<dist[i]<<" ";
    else
        fout<<"Ciclu negativ!"<<'\n';
}