#include <fstream>
#include <cstdio>
#define infi 1<<30
using namespace std;

ofstream fout("bellmanford.out");
int n,que[50001],Q[50001],C[50001],viz[50001],OK;
struct nod{
    nod *urm;
    int inf,cost;
}*L[50001];

inline void adauga(int &a, int &b, int &c){
    nod *p=new nod;
    p->inf=b;
    p->cost=c;
    p->urm=L[a];
    L[a]=p;
}

void bell(int k){
    int p,u,q;
    nod *vec;
    Q[1]=k;
    p=u=1;
    que[1]=1;
    while(p<=u){
        q=Q[p++];
        viz[q]++;
        if(viz[q]>n){
            OK=1;
            break;
        }
        vec=L[q];
            while(vec){
                if(C[vec->inf]>vec->cost+C[q]){
                    C[vec->inf]=vec->cost+C[q];
                    if(!que[vec->inf])
                        que[vec->inf]=1,Q[++u]=vec->inf;
                }
                vec=vec->urm;
            }
    que[q]=0;
    }
    if(OK==0)
        for(int i=2;i<=n;i++)
            fout<<C[i]<<' ';
    else
        fout<<"Ciclu negativ!";
}

int main()
{
    int i,a,b,c,m;
    FILE*fin=freopen("bellmanford.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&a,&b,&c);
        adauga(a,b,c);
    }
    for(int i=2;i<=n;i++)
        C[i]=infi;
    bell(1);
    return 0;
}