#include<fstream>
#include<queue>
#include<vector>
using namespace std;
ifstream f("date.in");
ofstream g("date.out");
#define inf 2000000000
vector <int> A[50001];
vector <int> C[50001];
queue <int> Q;
int d[50001], nrv[50001], incoada[50001];
int main(){
	int n, m, i, j, x,y,c, k, ok = 1;
	f >> n >> m;
	for( i = 1; i <= m; i++ )
	{
		f >> x >> y >> c;
		A[x].push_back(y);
		C[x].push_back(c);
	}
	for(i = 1; i <= n; i++)
		d[i] = inf;
	d[1] = 0;
	Q.push(1);
	incoada[1] = 1;
	nrv[1] = 1;
	while(!Q.empty() && ok == 1){
		k = Q.front();
		incoada[k] = 0;
		Q.pop();
		for(i = 0; i < A[k].size(); i++){
			if(d[A[k][i]] > d[k] + C[k][i] && C[k][i] != inf){
				d[A[k][i]] = d[k] + C[k][i];
				if(incoada[A[k][i]] == 0){
					Q.push(A[k][i]);
					nrv[A[k][i]]++;
					incoada[A[k][i]] = 1;
					if(nrv[A[k][i]] == n)
						ok = 0;
				}
			}
		}
				
	}
	if( ok == 0)
		g << "Ciclu negativ!";
	else
		for(i = 2; i <= n; i++)
			g << d[i] << " ";
	return 0;
}