#include<stdio.h>
struct nod
{
	int inf;
	int cost;
	nod *ad;
};

int viz[50001],c[50001],n,m,k=1,s[500001];
nod *l[250001],*a,*p;

void add(int x, int y,int z)
{
    a=new nod;
    a->inf=y;
    a->cost=z;
    a->ad=l[x];
    l[x]=a;
}

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d %d",&n,&m);
    int x,y,z;
    for(int i=1;i<m;i++)
        {
            scanf("%d %d %d",&x,&y,&z);
            add(x,y,z);
        }

    for(int i=0;i<=n;i++)
        c[i]=9999999;

    s[k]=1;
    viz[k]=1;
    c[k]=0;

    for(int i=1;i<=k;i++)
	{
		p=l[s[i]];
		while(p)
		{
			if( p->cost+c[s[i]] < c[p->inf] )
			{
				c[p->inf]=p->cost+c[s[i]];
				s[++k]=p->inf;
				viz[p->inf]++;
				if(viz[p->inf]>=n)
				{
					printf("Ciclu negativ!");
					return 0;
				}
			}
			p=p->ad;
		}
	}
	
    for(int i=2;i<=n;i++)
        printf("%d ",c[i]);
		
    return 0;
}