#include<stdio.h>
int m,c,n,i,j,k,l,r,p,d[50001],e[1500000],g[50001][50001],h[50001][50001];
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;
	while(m--)
     	scanf("%d%d%d",&i,&j,&c),g[i][w[i]++]=j,h[i][j]=c;
	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][g[j][i]])
        d[g[j][i]]=d[j]+h[j][g[j][i]],e[r++]=h[j][g[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]);
}