#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 51000
#define M 250010
#define MOD 50999
#define DMAX 250000000

using namespace std;

int h[N];
int dist[N],viz[N],nrrep[N];
int ifin;
struct muc{
    int next,vec,val;
};
muc lis[M];

int que[N],head,tail;

void push(int x){
    nrrep[x]++;
    viz[x]=1;
    que[head]=x;
    head=(head+1)%MOD;
}
int pop(){
    static int t;
    t=tail;
    viz[ que[t] ]=0;
    tail=(tail+1)%MOD;
    return que[t];
}


void Add_arc(int x,int y,int val);

int main(){
    int n,m;
    int x,y,d;
    int i,k;

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

    scanf("%d%d",&n,&m);

    memset(h,-1,(n+1)*4);
    for(i=1;i<=n;i++){
        dist[i]=DMAX;
    }

    for(i=0;i<m;i++){
        scanf("%d%d%d",&x,&y,&d);
        Add_arc(x,y,d);
    }

    push(1);
    dist[1]=0;
    while(head>tail){
        x=pop();
        for(i=h[x] ; i!=-1 ; i=lis[i].next){
            d=lis[i].val;
            y=lis[i].vec;
            if(dist[x]+d<dist[y]){
                dist[y]=dist[x]+d;
                if(viz[y]==0){
                    push(y);
                    if(nrrep[y]==n){
                        printf("Ciclu negativ!");
                        exit(0);
                    }
                }
            }
        }
    }
    for(i=2;i<=n;i++){
        printf("%d ",dist[i]);
    }

    return 0;
}
void Add_arc(int x,int y,int val){
    lis[ifin].vec=y;
    lis[ifin].val=val;
    lis[ifin].next=h[x];
    h[x]=ifin;
    ifin++;
}