#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 50000;
const int INF  = (1 << 30);

struct Edge
{
    int to, cost, cnt;
};

vector<Edge> G[NMAX+2];
int N, M, bad = 0;
int best[NMAX+2];

int main()
{
    in >> N >> M;
    for( int i = 1;  i <= N;  ++i ) best[i] = INF;
    for( int i = 1;  i <= M;  ++i ) {
        int x,y,c;
        in >> x >> y >> c;
        G[x].push_back({y,c,0});
      ///  G[y].push_back({x,c,0});
    }
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    best[1] = 0;
    pq.push({0, 1});
    while( !pq.empty() && !bad ) {
        int nod = pq.top().second;
        pq.pop();

        for( Edge &ed : G[nod] ) {
            if( best[nod] + ed.cost >= best[ed.to] ) continue;
            ed.cnt++;
            if( ed.cnt >= N ) {
                bad = 1;
                break;
            }
            best[ed.to] = best[nod] + ed.cost;
            pq.push({best[ed.to], ed.to});
        }
    }
    if( bad ) {
        out << "Ciclu negativ!\n";
        return 0;
    }
    for( int i = 2;  i <= N;  ++i ) out << best[i] << " \n"[i == N];
    return 0;
}