#include<fstream>
#include<vector>
#include<deque>
using namespace std;
const int MAX=99999999;
const int N=50000;
struct edge { int y,cost; };
vector<edge> v[N];
deque <int> coada;
int n,m,d[N],cont[N];

bool bford()
{   d[1]=0;int x;
	for (int i=2;i<=n;i++)
		d[i]=MAX;
    coada.push_back(1);
	while (!coada.empty())
	{
		x=coada.front();
		if (d[x]!=MAX)
			for (int i=0;i<v[x].size();i++)
			{
				if (d[v[x][i].y]>d[x] + v[x][i].cost)
				{
					d[v[x][i].y]=d[x]+v[x][i].cost;
					coada.push_back(v[x][i].y);
					cont[v[x][i].y]+=1;
					if ( cont[v[x][i].y]> n-1 ) return 0;
				}
			}
		coada.pop_front();
	}
	return 1;
}
int main()
{edge r;int x;
fstream f("bellmanford.in",ios::in);
fstream g("bellmanford.out",ios::out);
f>>n>>m;
for(int i=1;i<=m;i++)
{
    f>>x>>r.y>>r.cost;
    v[x].push_back(r);
}
if(bford()==0)
g<<"Ciclu negativ!";
else
for(int j=2;j<=n;j++)
g<<d[j]<<" ";

return 0;
}