#include <cstdio>
#define maxn 50010
#define maxm 250010
#define INF 0x3f3f3f3f
struct muchie {int x,y,c;} e[maxm];
int n,m,i,j,k,cost[maxn];

int ciclu()
{
    for(int i=1;i<=m;++i)
        if(cost[e[i].x]+e[i].c<cost[e[i].y])
            return 1;
    return 0;
}         

int main()
{
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i)
        scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].c);
	
	for(i=2; i<=n; ++i)
        cost[i]=INF;
	for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
            if(cost[e[j].x]+e[j].c<cost[e[j].y])
                cost[e[j].y]=cost[e[j].x]+e[j].c;
    if(ciclu())
        printf("Ciclu negativ!\n");
	else
		for(i=2; i<=n; ++i)
			printf("%d ", cost[i]);
    return 0;
}