#include <stdio.h>
#define DIM 50005
#define DIM2 250010

struct nod{int x,c; 
           nod* urm;} *lst[DIM];
struct cell{int x,y,c;} muchie[DIM2];

int a[DIM], n, m, v[DIM];

void add(int a, int b, int cost)
{
    nod *p= new nod;
    p->x=b;
    p->c=cost;
    p->urm=lst[a];
    lst[a]=p;
    }

void read()
{

    scanf("%d%d",&n,&m);
    for (int i=1; i<=n; ++i)
    {
        scanf("%d%d%d",&muchie[i].x,&muchie[i].y,&muchie[i].c);
        add(muchie[i].x,muchie[i].y,muchie[i].c);
        }
    }
    
int ford()
{
    int st,dr,c[250100], aux;
    long long k=1;
    c[st=dr=1]=v[1]=1;
    nod *p=new nod;
    while (st<=dr)
    {
        aux=c[st%DIM2];
        for (p=lst[aux]; p; p=p->urm)
            if (a[aux]+p->c<a[p->x])
            {
                a[p->x]=a[aux]+p->c;      
                v[p->x]=1;                 
                ++dr;    
                c[dr%DIM2]=p->x; 
                }
        ++st;
        if (++k>(long long)n*m) return 0;     
        }
        for(int i=1;i<=m;++i) 
            if(a[muchie[i].x]+muchie[i].c<a[muchie[i].y])           
                return 0;
        return 1; 
    }

void print()
{
    for (int i=2; i<=n; ++i)
        printf("%d ", a[i]);
    }
    
int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    read();
    if (ford()) print();
        else printf("Ciclu negativ!\n");
    return 0;
    }