#include <cstdio>
#include <set>
#include <vector>
using namespace std;
struct aa{int b;int c;};
struct aaa{int a;int b;int c;};
int dist[50002],n,m;
vector <aa> g[50002];
vector <aaa> muchii;
set <int> nodes;
set <int>::iterator it;
void bf()
{
		dist[1]=0;
		int i,node,l,j,son,costs;
		for(i=2;i<=n;i++)
			dist[i]=2000000000;
		for(i=1;i<=n-1;i++)
			for(it=nodes.begin();it!=nodes.end();it++)
			{
				node=*it;
				l=g[node].size();
				for(j=0;j<l;j++)
				{
					son=g[node][j].b;
					costs=g[node][j].c;
					if(dist[son]>dist[node]+costs)
					{
						dist[son]=dist[node]+costs;
						nodes.insert(son);
					}
				}
			}
}
int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    int i,a,b,c;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
		{
			scanf("%d%d%d",&a,&b,&c);
			g[a].push_back({b,c});
			muchii.push_back({a,b,c});
		}
		nodes.insert(1);
		bf();
		a=muchii.size();
		for(i=0;i<a;i++)
			if(dist[muchii[i].a]+muchii[i].c<dist[muchii[i].b])
		{
			printf("Ciclu negativ!");
			return 0;
		}
		for(i=2;i<=n;i++)
			printf("%d ",dist[i]);
    return 0;
}