#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>

#define BUF_SIZE 1<<17
char buf[BUF_SIZE];
int pbuf=BUF_SIZE;
FILE*fi,*fo;
inline char nextch(){
    if(pbuf==BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fi);
        pbuf=0;
    }
    return buf[pbuf++];
}
inline long long nextnum(){
    long long a=0;
    char c=nextch();
    while((c<'0' || c>'9') && c!='-')
        c=nextch();
    int semn=1;
    if(c=='-'){
        semn=-1;
        c=nextch();
    }
    while('0'<=c && c<='9'){
        a=a*10+c-'0';
        c=nextch();
    }
    return a*semn;
}

#define MAXN 50000
#define MAXQ 65535

struct Edge{
    int node;
    int cost;
};
std::vector <Edge> G[1+MAXN];
int q[MAXQ];
int dist[1+MAXN];
int app[1+MAXN];
int inq[1+MAXN];

int main(){
    fi=fopen("bellmanford.in","r");
    fo=fopen("bellmanford.out","w");
    int n=nextnum(), m=nextnum();
    for(int i=0;i<m;i++){
        Edge temp;
        int x=nextnum();
        temp.node=nextnum();
        temp.cost=nextnum();
        G[x].push_back(temp);
    }
    for(int i=1;i<=n;i++)
        dist[i]=1000000000;
    int p=0, u=1;
    q[0]=1;
    dist[1]=0;
    inq[1]=1;
    int flag=1;
    while(p!=u && flag){
        int node=q[p];
        for(int i=0;i<G[node].size();i++)
            if(dist[node]+G[node][i].cost<dist[G[node][i].node]){
                dist[G[node][i].node]=dist[node]+G[node][i].cost;
                app[G[node][i].node]++;
                if(app[G[node][i].node]==n)
                    flag=0;
                if(!inq[G[node][i].node]){
                    inq[G[node][i].node]=1;
                    q[u]=G[node][i].node;
                    u++;
                    u=u&MAXQ;
                }
            }
        inq[node]=0;
        p++;
        p=p&MAXQ;
    }
    if(!flag)
        fprintf(fo,"Ciclu negativ!");
    else{
        for(int i=2;i<=n;i++)
            fprintf(fo,"%d ", dist[i]);
    }
    fclose(fi);
    fclose(fo);
    return 0;
}