#include<fstream>
#include<vector>
#include<queue>
using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

#define nmax 50002
#define inf 1000000000

typedef struct structura{int vec,pret;};
int n,m,cost[nmax],l[nmax],viz[nmax]; structura x;
vector <structura> nod[nmax];
queue <int> q;

void citire()
{
	f>>n>>m; int i,j;
	
	for(i=1;i<=m;i++)
	{
		f>>j>>x.vec>>x.pret;
		nod[j].push_back(x);
	}
	for(i=1;i<=n;i++)
		l[i]=nod[i].size();
}
void init()
{
	for(int i=2;i<=n;i++)
		cost[i]=inf;
}
int main()
{
	int i,p;
	citire();init();
	q.push(1);
	while(!q.empty())
	{
		p=q.front();q.pop();
		viz[p]++;
		if(viz[p]>m)
		{
			g<<"Ciclu negativ!\n";
			return 0;
		}
		for(i=0;i<l[p];i++)
		{
			x=nod[p][i];
			if(cost[x.vec]>cost[p]+x.pret)
			{
				q.push(x.vec);
				cost[x.vec]=cost[p]+x.pret;
			}
		}
	}
	for(i=2;i<=n;i++)
		g<<cost[i]<<" ";
}