#include <fstream>
#include <vector>
#include <queue>
#define NMAX 50005
#define INFINIT 33333

using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

struct edge
{
	int nod, c;
};

vector <edge> a[NMAX];
int dmin[NMAX], nr[NMAX];

queue <int> q;

int n, m, k;

void citire();
bool Bellman_Ford();
void afisare();

int main()
{
	citire();
	afisare();

	return 0;
}

void citire()
{ int i, x;
edge muchie;
muchie.nod = muchie.c = 0;
fin >> n >> m;
for(i=1; i<=n+1; i++)
   {a[i].push_back(muchie);
    dmin[i]=INFINIT;
   }
dmin[1] = 0;
for(i=1; i<=m; i++)
   {fin>>x>>muchie.nod>>muchie.c;
    a[x].push_back(muchie);
    a[x][0].c++;
   }
	q.push(1);
}

bool Bellman_Ford()
{int i, x;
bool negative_circuit=0;
while(!q.empty()&&!negative_circuit)
	 {x=q.front();
	  q.pop();
      for(i=1; i<=a[x][0].c; i++)
          if(dmin[a[x][i].nod]>dmin[x]+a[x][i].c)
			{dmin[a[x][i].nod]=dmin[x]+a[x][i].c;
             nr[a[x][i].nod]++;
             if(nr[a[x][i].nod]==n)
               {negative_circuit=1;
                break;
               }
             q.push(a[x][i].nod);
			}
	  }
return negative_circuit;
}

void afisare()
{if(Bellman_Ford())
    fout<<"Ciclu negativ!\n";
	else
	{for(int i=2; i<=n; i++)
         fout << dmin[i] << ' ';
     fout << '\n';
	}
}