#include <bits/stdc++.h>
#define NMAX 50005
#define MMAX 250005
#define INF (1<<30)
using namespace std;

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

bool ciclu_negativ = false;
int n, m, dist[NMAX];
vector < pair <int, int> > A[NMAX];
vector <int> cnt_queue(MMAX, 0);
bitset <NMAX> inCoada;
queue <int> Q;

void read()
{
    in>>n>>m;
    for(int i = 1; i<=m; i++) {
        int x, y, z;
        in>>x>>y>>z;
        A[x].push_back({y, z});
    }

}

void Bellman(int x)
{
    for(int i = 1; i<=n; i++)
        dist[i] = INF;
    dist[x] = 0;

    Q.push(x);
    inCoada[x] = true;

    while(!Q.empty() && !ciclu_negativ) {
        int Nod = Q.front();
        Q.pop();
        inCoada[Nod] = false;

        for(auto k : A[Nod]) {
            int Vecin = k.first;
            int Cost = k.second;

            if(dist[Vecin] > dist[Nod] + Cost) {
                dist[Vecin] = dist[Nod] + Cost;

                if(!inCoada[Vecin]) {
                    if(cnt_queue[Vecin] > n)
                        ciclu_negativ = true;
                    else {
                        Q.push(Vecin);
                        inCoada[Vecin] = true;
                        cnt_queue[Vecin]++;
                    }
                }
            }
        }
    }

}


int main()
{

    read();
    Bellman(1);
    if(!ciclu_negativ) {
        for(int i = 2; i<=n; i++)
            out<<dist[i]<<' ';
    } else out<<"Ciclu Negativ!";

    return 0;
}