#include<fstream>
#include<vector>
#include<queue>
#define inf 0x3f3f3f
using namespace std;
struct nod
{
	int y,c;
};
vector<vector<nod> > mat(50000);
vector<int> dist(50001,inf);
queue<int> q;
int n,i,x,y,c,m;
int main()
{
	ifstream f("bellmanford.in");
	ofstream g("bellmanford.out");
	f>>n>>m;
	for(;m;--m)
	{
		f>>x>>y>>c;
		mat[x].push_back( (nod) {y,c} );
	}
	dist[1]=0;
	q.push(1);
	while(!q.empty())
	{
		x=q.front();
		for(i=0;i<mat[x].size();++i)
			if( dist[ mat[x][i].y ] > dist[x]+ mat[x][i].c )
			{
				dist[mat[x][i].y]=dist[x]+mat[x][i].c;
				q.push(mat[x][i].y);
			}
			else 
				if(dist[ mat[x][i].y ]>0 && dist[x]<0)
{
               g<<"Ciclu negativ!";
                    return 0;
}
	q.pop();
	}
	for(i=2;i<=n;++i)
		if(dist[i]!=inf)
			g<<dist[i]<<" ";
		else
			g<<0<<" ";
}