#include <bits/stdc++.h>

using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

const int INF = 2000000000;
const int NMAX = 50005;

struct Muchie {
    int u,v,c;
};
int N,M;
vector<Muchie> muchii;
int D[NMAX];
void bellmanford(int sursa)
{
    for(int i=1; i<=N; i++) {
        D[i]=INF;
    }
    D[sursa]=0;
    for(int i=1;i<=N-1;i++) {
        bool schimbare=false;
        for(auto& edge : muchii) {
            if(D[edge.u]!=INF && D[edge.u]+edge.c<D[edge.v]) {
                D[edge.v]=D[edge.u]+edge.c;
                schimbare=true;
            }
        }
        if(!schimbare)
            break;
    }
    bool cicluNegativ=false;
    for(auto& edge : muchii) {
        if (D[edge.u]!=INF && D[edge.u]+edge.c<D[edge.v]) {
            cicluNegativ=true;
            break;
        }
    }
    if(cicluNegativ)
        g<<"Ciclu negativ!\n";
    else
    {
        for(int i=2;i<=N;i++) {
            g<<D[i]<<" ";
        }
        g<<"\n";
    }
}
int main()
{
    f>>N>>M;
    int x,y,c;
    for(int i=0;i<M;i++)
    {
        f>>x>>y>>c;
        muchii.push_back({x,y,c});
    }
    bellmanford(1);
    return 0;
}