#include <iostream>
#include <fstream>
#define NMAX 10000
#define INFINIT 210000000
using namespace std;

long n,m,i,j,k,d[NMAX],tata[NMAX];
int C[NMAX][NMAX];

int bellman_ford(int x0) 
{
   int ok, i, j, k;
   for (i=1;i<=n;i++) {
      tata[i] = 0; d[i] = INFINIT;}
   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]!=INFINIT && C[j][k]!=INFINIT)
               if (d[k]>d[j]+C[j][k])
               {
                  d[k] = d[j]+C[j][k];
                  tata[k] = j;
                  ok = 1;
               }
   } 
   if (ok == 1) cout<<"Circuit negativ!";
   return ok;
}

int main ()
{
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	i=INFINIT;
	f>>n>>m;
	for (i=1; i<=n; i++)
		for (j=1; j<=n; j++)
			if (i==j) C[i][j]=0;
			else C[i][j]=INFINIT;
			
	for (i=1; i<=m; i++)
	{
		f>>j>>k;
		f>>C[j][k];
	}
	
	bellman_ford(1);
	
	for (i=2; i<=n; i++) if (d[i]==INFINIT) g<<0<<" "; else g<<d[i]<<" ";
	f.close(); g.close();
	return 0;
}