#include<cstdio>
#include<vector>
#include<deque>
#include<bitset>
#define oo 99999
using namespace std;
vector<pair<int,int> >V[50010];
bitset<50010> viz;
deque<int> Q;
int n,m,x,y,z,cost[50010],nr[50010],ok=1,i;
void read(),solve();
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(;m;--m)
	{
		scanf("%d%d%d",&x,&y,&z);
		V[x].push_back(make_pair(y,z));
	}
}
void solve()
{
	//memset(cost,99999,sizeof(cost));
	for(i=1;i<=n;i++)cost[i]=50000010;
	Q.push_back(1);cost[1]=0;viz[1]=1;
	for(;!Q.empty()&&ok;)
	{
		deque<int>::iterator q=Q.begin();
		Q.pop_front();
		viz[*q]=0;
		for(vector<pair<int,int> >::iterator it=V[*q].begin();it!=V[*q].end();it++)
			if(cost[it->first]>cost[*q]+it->second)
			{
				cost[it->first]=cost[*q]+it->second;
				if(!viz[it->first])
				{
					if(nr[it->first]>n){ok=0;break;}
					viz[it->first]=1;
					Q.push_back(it->first);
					++nr[it->first];
				}
			}
	}
	if(!ok){printf("Ciclu negativ!\n");return;}
	for(i=2;i<=n;i++)printf("%d ",cost[i]);
}