#include <cstdio>
#include <vector>
#include <queue>
#define INF 1000000000
#define NMAX 50001

using namespace std;

int n, x0;
vector < pair<int,int> > G[NMAX];
int dmin[NMAX];
int nr[NMAX];
bool negativ;
queue<int> C;

void citire();
void bellman_ford();
void afisare();

int main()
{
 citire();
 bellman_ford();
 afisare();
 return 0;
}

void citire()
{int i, m, x, y, c;
 FILE * fin=fopen("bellmanford.in","r");
 fscanf(fin,"%d %d", &n, &m); x0=1;
 for (i=0; i<m; i++)
     { fscanf(fin,"%d %d %d", &x, &y, &c);
       G[x].push_back(make_pair(y,c)); }
}

void bellman_ford()
{vector< pair<int,int> > ::iterator it;
 int i, x;
 for (i=1; i<=n; ++i) dmin[i]=INF;
 dmin[x0]=0;
 C.push(x0);
 while (!C.empty()&& !negativ)
        {x=C.front(); C.pop();
         for (it = G[x].begin(); it != G[x].end(); ++it)
            if (dmin[it->first] > dmin[x] + it->second)
			   { dmin[ it->first ]=dmin[x] + it->second;
                 nr[ it->first ]++;
                 C.push(it->first);
                 if (nr[it->first] > n)negativ=true;
               }
        }
}

void afisare()
{FILE * fout=fopen("bellmanford.out","w");
 if (negativ)
	 fprintf(fout,"Ciclu negativ!\n");
     else
     {
      for (int i=1; i<=n; i++)
	      if (i!=x0)
		     fprintf(fout,"%d ", (dmin[i]!=INF)?dmin[i]:0);
      fprintf(fout,"\n");
     }
 fclose(fout);
}