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

	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]=1000000;
	
cost[1]=0;		
Q.push(1);
v[1]=1;

	while(!Q.empty())
	{
		for(int i=0;i<lista[Q.front()].size();i++)
		{
			if(/*v[lista[Q.front()][i].first]!=1 &&*/ cost[Q.front()]+lista[Q.front()][i].second<cost[lista[Q.front()][i].first] )
			{
				Q.push(lista[Q.front()][i].first);
				cost[lista[Q.front()][i].first]=cost[Q.front()]+lista[Q.front()][i].second;
				v[lista[Q.front()][i].first]++;
				
			}
			if(v[lista[Q.front()][i].first]>=n) 
				{
					g<<"Ciclu negativ!";
					return 0;
			}
		}
			v[Q.front()]=0;
			Q.pop();
	}
	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]<<" ";
		
}