#include<fstream>
#include<vector>
#include<queue>
#include<stdlib.h>
#define maxn 50010
#define inf 1<<30 
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

vector<pair<int,int> > a[maxn];
queue<int> q;
int cnt[maxn];
bool inqueue[maxn];
int n,m;
int d[maxn];
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));
	}
}
void bellmanford()
{
	q.push(1);
	for(int i=1;i<=n;i++)
		d[i]=inf;
	inqueue[1]=true;
	d[1]=0;
	while(!q.empty())
	{
		int nod=q.front();
		q.pop();
		inqueue[nod]=false;
		vector<pair<int,int> >::iterator it;
		for(it=a[nod].begin();it!=a[nod].end();it++)
		{
			if(d[it->first]>d[nod]+it->second)
			{
			    d[it->first]=d[nod]+it->second;
				if(inqueue[it->first]==false)
				{
					q.push(it->first);
					inqueue[it->first]=true;
					cnt[it->first]++;
					if(cnt[it->first]>n) {out<<"Ciclu Negativ!";exit(0);}
				}
			}
		}
	}
}

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