#include <cstdio>
#define MAX 50001
#define INF 0xEEA8310

struct muchie{ int st,dr,c; }u[4*MAX];
int dist[MAX],n,m;

void bellman_ford(){
    bool ok;
    int k,i;
    dist[1]=0;
    for(k=2;k<=n;k++){
        ok=false;
        for(i=1;i<=m;i++)
        if(dist[u[i].st]+u[i].c<dist[u[i].dr]){
            ok=true;
            dist[u[i].dr]=dist[u[i].st]+u[i].c; } }
    if(ok)printf("Ciclu Negativ!"); else {
        for(i=2;i<=n;i++)printf("%d ",dist[i]); }
}

int main(){
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
        scanf("%d %d",&n,&m);
        for(int i=1;i<=m;i++)
        scanf("%d %d %d",&u[i].st,&u[i].dr,&u[i].c);
        for(int i=1;i<=n;i++)dist[i]=INF;
    bellman_ford();
}