#include<fstream>
#include<vector>
#include<queue>
using namespace std;

#define inf 0x3f3f3f3f
	ofstream g("bellmanford.out");
int cost[50002],v[50002],n,m;

vector <pair <int,int> > lista[50002];
queue <int> Q;

int bell()
{
	for(int i=1;i<=n;i++) cost[i]=inf;
	
	cost[1]=0;		
	Q.push(1);
	v[1]=1;

	while(!Q.empty())
	{
		int nod = Q.front();
		Q.pop();
		
		for(unsigned int i=0;i<lista[nod].size();i++)
		{
			int nod2 = lista[nod][i].first;
			int cost2 = lista[nod][i].second;
			
			if (cost[nod2] <= cost[nod] + cost2) continue;
			
			v[nod2] ++;
			
			if(v[nod2] > n) 
			{
				g<<"Ciclu negativ!";
				return 0;
			}
			
			cost[nod2] = cost[nod] + cost2;
			
			Q.push (nod2);
		}
	}
	
	return 1;
}

int main()
{
	ifstream f("bellmanford.in");

	f>>n>>m;
	int x,y,z;
	
	for(int i=1;i<=n;i++)
	{
		f>>x>>y>>z;
		lista[x].push_back(make_pair(y,z));
	
	}
	
	if(bell())
	
	for(int i=2;i<=n;i++)
		g<<cost[i]<<" ";
		
}