#include <fstream>
#include <vector>
#include <queue>
#define NMAX 50001
#define MMAX 250001
#define y first
#define cost second
using namespace std;

const int inf=2000000000;
int D[NMAX], U[NMAX], i, j, c, n, m, ok, inQ[NMAX];

vector< pair<int, int> > G[NMAX];
queue<int> Q;

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

bool Bell()
{	Q.push(1);
	U[1]=1;
	inQ[1]=1;
	while (!Q.empty())
	{	int nod=Q.front();
		Q.pop();
		inQ[nod]=0;
		++U[nod];
		if (U[nod]==n)
			return 0;
		vector< pair<int, int> >::iterator it;
		for (it=G[nod].begin(); it!=G[nod].end(); ++it)
			if (D[it->y]>D[nod]+it->cost)
			{	D[it->y]=D[nod]+it->cost;
				if (!inQ[it->y])
				{	inQ[it->y]=1;
					Q.push(it->y);
				}
			}
	}
	return 1;
}

int main()
{	f>>n>>m;
	for (; m; --m)
	{	f>>i>>j>>c;
		G[i].push_back(make_pair(j, c));
	}
	for (i=2; i<=n; ++i)
		D[i]=inf;
	if (!Bell())
		g<<"Ciclu negativ!\n";
	else
	{	for (i=2; i<=n; ++i)
			g<<D[i]<<' ';
		g<<'\n';
	}
    return 0;
}