#include<stdio.h>
#include<vector>
#define nmax 60000
#define mmax 260000
#define inf 9999999

using namespace std;

vector<int> g[nmax];
int i,j,m,n, que[nmax], nr, viz[nmax], cost[nmax], nod, poz;
struct asd{int a;int b;int c;}muchie[mmax];


int negativ()
{
    int i;
    for(i=1; i<=m; i++)
        if(cost[muchie[i].a]+muchie[i].c<cost[muchie[i].b])
            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", &muchie[i].a, &muchie[i].b, &muchie[i].c);
		g[muchie[i].a].push_back(i);
	}
	cost[1]=0;
	for(i=2; i<=n; i++)
        cost[i]=inf;
    nr=1;
    que[1]=1;
    viz[1]=1;
	for(i=1;i<=nr&&1LL*i<=1LL*n*m;i++)
    {
		nod=que[i%n];
        viz[nod]=0;
        for(j=0;j<g[nod].size();j++)
        {
            poz=g[nod][j];
            if(cost[muchie[poz].a]+muchie[poz].c<cost[muchie[poz].b])
            {
                cost[muchie[poz].b]=cost[muchie[poz].a]+muchie[poz].c;
                if(!viz[muchie[poz].b])
                {
                    viz[muchie[poz].b]=1;
                    ++nr;
                    que[nr%n]=muchie[poz].b;
                }
            }
        }

	}
	if(negativ())
    {
        printf("Ciclu negativ!\n");
        return 0;
    }
    for(i=2; i<=n; i++)
        printf("%d ", cost[i]);
	return 0;
}