#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
const int inf=1e9+5;
vector<int>dist(50001,inf);
vector<int>cnt(50001,0);
vector<int>inQ(50001,0);
int n,m,a,b,c;
vector<vector<pair<int,int>>>LA;
int main()
{
	f>>n>>m;
	LA.resize(n+1);
	for(int i=0;i<m;i++)
	{
		f>>a>>b>>c;
		LA[a].push_back({b,c});
		// LA[b].push_back({a,c});
	}
	int s=1;
	dist[s]=0;
	cnt[s]=1;
	queue<int>q;
	q.push(s);
	inQ[s]=1;
	while(!q.empty())
	{
		int nod=q.front();
		q.pop();
		inQ[nod]=0;
		for(auto it:LA[nod])
		{
			int vecin=it.first;
			int cost=it.second;
			if(dist[nod]+cost<dist[vecin])
			{
				dist[vecin]=dist[nod]+cost;
				if(inQ[vecin]==0)
				{
					q.push(vecin);
					inQ[vecin]=1;
					cnt[vecin]++;
					if(cnt[vecin]>n)
					{
						g<<"Ciclu negativ!\n";
						return 0;
					}
				}
			}
		}
	}
	for(int i=2;i<=n;i++)
	{
		if(dist[i]==inf)g<<0<<" ";
		else g<<dist[i]<<" ";
	}

}