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

int n, m, dist[NMAX], viz[NMAX];
vector < pair <int, int> > A[NMAX];
bitset <NMAX> inCoada;
queue <int> Q;

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

}

int 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()) {
        int a = Q.front();
        inCoada[a] = false;
        viz[a]++;

        if(viz[a] > n)
            return false;

        Q.pop();

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

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


                if(!inCoada[Vecin]) {
                    Q.push(Vecin);
                    inCoada[Vecin] = true;
                }
            }
        }

    }
    return true;
}

int main()
{
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);

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

    return 0;
}