#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#define NMAX 50001
#define INF 1e8
using namespace std;

struct ura
{
    int nod, cost;
}aux;

int n,m,cnt[NMAX];
vector <ura>adj[NMAX];
bool InCoada[NMAX];
queue <int>coada;
int D[NMAX];

int main() {
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    int x,y,c,u,v;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>c;
        aux.nod=y;
        aux.cost=c;
        adj[x].push_back(aux);
    }
    for(int i=2;i<=n;i++)
        D[i]=INF;
    coada.push(1);
    cnt[1]++;
    InCoada[1]=true;
    while(!coada.empty())
    {
        v=coada.front();
        coada.pop();
        InCoada[v]=false;
        vector<ura>::iterator it;
        for(it=adj[v].begin();it!=adj[v].end();it++)
        {
            u=(*it).nod;
            c=(*it).cost;
            if(D[u]>D[v]+c)
            {
                if(!InCoada[u])
                {
                    coada.push(u);
                    cnt[u]++;
                    InCoada[u]=true;
                }
                D[u]=D[v]+c;
            }
            if(cnt[u]>=n)
            {
                cout<<"Ciclu negativ!";
                return 0;
            }
        }
    }
    for(int i=2;i<=n;i++)
        cout<<D[i]<<' ';
    return 0;
}