#include<fstream.h>
#include<vector>

using namespace std;

vector < pair <int, int> > v[50100];
int bagat [50100], sw[50100], dist[50100],C[50100],n;

int bell ()
{
	vector< pair<int, int> > ::iterator it;
	int c,p,u,inf,i,ok;
	inf =2000000000;
	for (i=2;i<=n;i++)
		dist[i]=inf;
	
	p=u=1;
	C[p]=1;
	bagat[1]=1;
	sw[1]++;
	ok=1;
	
	while (ok && p<=u)
	{
		c=dist[C[p]];
		for (it=v[C[p]].begin();it<v[C[p]].end();++it)
			if (dist[it->first]>it->second+c)
			{
				dist[it->first]=it->second+c;
				if (!bagat[it->first])
				{
					bagat[it->first]=1;
					sw[it->first]++;
					if (sw[it->first]>n)
						ok=0;
					C[++u]=it->first;
				}
			}
		bagat[C[p]]=0;
		p++;
	}
	
	return ok;
}		

void afisare (int ok)
{
	ofstream g("bellmanford.out");
	if (!ok)
		g<<"Ciclu negativ!";
	else
	{
		int i;
		for (i=2;i<=n;i++)
			g<<dist[i]<<' ';
	}
	g.close();
}
void citire()
{
	int i,a,b,c,m;
	vector< int> :: iterator it;
	ifstream f("bellmanford.in");
	f>>n>>m;
	for (i=1;i<=m;++i)
	{
		f>>a>>b>>c;
		v[a].push_back(make_pair(b,c));
	}
	f.close();
}

int main()
{
	int ok;
	citire();
	ok=bell();
	afisare(ok);
	return 0;
}