#include<stdio.h>
#include<stdlib.h>
int m,n,i,j,k,l,r,p,d[50001],e[1500000],*g[50001],*h[50001],w[50001],a[250001],b[250001],c[250001];
int main() {
	freopen("bellmanford.in","r",stdin),freopen("bellmanford.out","w",stdout),scanf("%d%d",&n,&m);
	for(i=2;i<=n;i++)
     	d[i]=50001;
	for(i=1;i<=m;i++)
     	scanf("%d%d%d",&a[i],&b[i],&c[i]),w[a[i]]++;
    for(i=1;i<=n;w[i++]=0)
        g[i]=(int*)malloc(w[i]*sizeof(int)),h[i]=(int*)malloc(w[i]*sizeof(int));
    for(i=1;i<=m;i++)
        g[a[i]][w[a[i]]]=b[i],h[a[i]][w[a[i]]++]=c[i];
	for(e[r++]=1;l<r&&!k;)
    for(j=e[l++],i=0;i<w[j];i++)
    if(d[g[j][i]]>d[j]+h[j][i])
        d[g[j][i]]=d[j]+h[j][i],e[r++]=h[j][i];
    else
        if(d[g[j][i]]>0&&d[j]<0)
            printf("Ciclu negativ!"),k=1;
	for(i=2;i<=n&&!k;i++)
     	printf("%d ",d[i]>0?(d[i]%50001):d[i]);
}