#include<cstdio>
#define maxn 5005
#define maxm 25005
#define INF 0x3f3f3f3f
using namespace std;
int tata[maxn],d[maxn],c[maxn][maxn],n,m,x,y,i,ev;

int bellman_ford(int x0) 
{
   int ok, i, j, k;
   for (i=1;i<=n;i++) {
      tata[i] = 0; d[i] = INF;}
   d[x0] = 0;
   for (i=1; i<=n; i++) 
   {
      ok = 0;
      for (j=1;j<=n;j++)
         for (k=1;k<=n;k++)
            if (d[j]!=INF && c[j][k]!=INF)
               if (d[k]>d[j]+c[j][k])
               {
                  d[k] = d[j]+c[j][k];
                  tata[k] = j;
                  ok = 1;
               }
   } 
   if (ok == 1) printf("Circuit negativ!");
   return ok;
}

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",&x,&y,&c[x][y]);
	ev=bellman_ford(1);
	if(ev==0)
		for(i=2;i<=n;++i)
			printf("%d ",d[i]);
	return 0;
}