#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)
{
	int cnt=0;
	queue<int> fifo;
	vector<pair<int,int> >:: iterator it;
	for(int i=1;i<=n;++i)
	{
		d[i]=INF;
	}
	d[1]=0;
	fifo.push(s);
	int k=n*m;
	while(!fifo.empty() && cnt<k)
	{
		int u = fifo.front();
		fifo.pop();
		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;
				fifo.push(it->first);
			}
		}
		cnt++;
	}
	if(cnt==k)
	{
		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;
}