#include<fstream>
#define maxn 50010
#include<vector>
#include<bitset>
#include<cstdlib>
#include<queue>
#define inf 1<<30
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
queue<int>q;
int cnt[maxn];
vector<pair<int,int> >a[maxn];
bool uz[maxn];
int d[maxn];
int n,m;
void read()
{
	in>>n>>m;
	int x,y,z;
	for(int i=1;i<=m;i++)
	{
		in>>x>>y>>z;
		a[x].push_back(make_pair(y,z));
	}
	for(int i=2;i<=n;i++)
		d[i]=inf;
}

void bellmanford()
{
	q.push(1);
	d[1]=0;
	uz[1]=true;
	while(!q.empty())
	{
		int nod=q.front();
		q.pop();
		uz[nod]=false;
		for(int i=0;i<a[nod].size();i++)
		{
			int nodc=a[nod][i].first;
			if(d[nodc]>d[nod]+a[nod][i].second)
			{
				d[nodc]=d[nod]+a[nod][i].second;
				if(uz[nodc]==false)
				{
					q.push(nodc);
					uz[nodc]=true;
					cnt[nodc]++;
					if(cnt[nodc]>n){out<<"Ciclu negativ!";exit(0);}
				}
			}
		}
	}
}

int main()
{
	read();
	bellmanford();
	for(int i=2;i<=n;i++)
	  out<<d[i]<<" ";
}