#include <cstdio>
#include <vector>
#include <queue>
#include <utility>
#define NMAX 50010
#define INF 0x3f3f3f3f

using namespace std;

int n,m;
vector<pair<int, int> > arcs[NMAX];
int d[NMAX];


int readInt()
{
	int n=0;
	int sign;
	char c=getchar();
	while((c<'0' || c>'9') && c!='-') c=getchar();
	if(c=='-'){ sign=-1; c=getchar();}
	else {sign=1;}
	while(c>='0' && c<='9')
	{
		n=(n<<1)+(n<<3)+c-'0';
		c=getchar();
	}
	return n*sign;
}

void Read()
{
	int a,b,d;
	freopen("bellmanford.in","r",stdin);
	n=readInt();
	m=readInt();
	for(int i=0;i<m;++i)
	{
		a=readInt();
		b=readInt();
		d=readInt();
		arcs[a].push_back(make_pair(b,d));
	}
}

bool Bellmanford(int s)
{
	vector<pair<int,int> >:: iterator it;
	for(int i=1;i<=n;++i)
	{
		d[i]=INF;
	}
	d[1]=0;
	for(int i=1;i<n;++i)
	{
		for(int u=1;u<=n;++u)
		{
			for(it=arcs[u].begin();it!=arcs[u].end();++it)
			{
				if(d[it->first]>d[u]+it->second)
				{
					d[it->first]=d[u]+it->second;
				}
			}
		}
	}
	for(int u=1;u<=n;++u)
	{
		for(it=arcs[u].begin();it!=arcs[u].end();++it)
		{
			if(d[it->first]>d[u]+it->second)
			{
				return false;
			}
		}
	}

	return true;
}

void Write(bool boolean)
{
	freopen("bellmanford.out","w",stdout);
	if(boolean==false)
	{
		printf("Ciclu negativ!\n");
	}
	else
	{
		for(int i=2;i<=n;++i)
		{
			printf("%d ",(d[i]!=INF)?d[i]:0);
		}
	}
}


int main()
{
	Read();
	bool boolean = Bellmanford(1);
	Write(boolean);
	return 0;
}