using namespace std;
#include<fstream>
#include<vector>
#include<queue>
#define MAX_N 50002
#define mk make_pair
#define oo 0x3f3f3f3f
vector<pair<int,int> >G[MAX_N];
unsigned N, M;
int viz[MAX_N], nr[MAX_N], d[MAX_N];
queue<int>Q;
bool negativ = false;
int main()
{
	ifstream f("bellmanford.in"); ofstream g("bellmanford.out");
	f>>N>>M;
	unsigned i; int x,y, cst;
	for(i=1;i<=M; ++i) 
	{
		f>>x>>y>>cst;
		G[x].push_back(mk(y,cst));
		
	}
	for(i=1;i<=N;++i) d[i] = oo;
	Q.push(1);  d[1] = 0;
	for(;!Q.empty() && !negativ;Q.pop())
	{
		x = Q.front(); viz[x] = 0;
		for(i = 0; i < G[x].size(); ++i)
		{
			y = G[x][i].first; cst = G[x][i].second;
			if( d[y] > d[x] + cst)
			{
				d[y] = d[x] + cst;
				if(!viz[y]) 
				{
					if(nr[y] > N) negativ = true;
					else 
					{
						viz[y] = 1; 
						++nr[y];					
						Q.push(y);
					}
				}
			}	
		}
	}
	if(negativ == true) g<<"Ciclu negativ!\n";
	else for(i=2;i<=N;++i) g<<d[i]<<" ";
	return 0;
}