#include<fstream>
#include<queue>
#include<vector>
#define Nmax 50001
#define INF 0x3f3f3f
using namespace std;
struct pereche
{
	int nod,cost;
}aux;
queue<int> Q;
vector<pereche> G[Nmax];
int viz[Nmax],N,M,in[Nmax],D[Nmax],ciclu_negativ;
void read()
{
	ifstream f("bellmanford.in");
	f>>N>>M;
	int i,x,y,c;
	for(i=1;i<=M;++i)
	{
		f>>x>>y>>c;
		aux.nod = y;
		aux.cost = c;
		G[x].push_back(aux);
	}
	f.close();
}
void bellmanford()
{
	int i,nod;
	for(i=1;i<=N;++i)
		D[i] = INF;
	Q.push(1);
	in[1] = 1;
	D[1] = 0;
	while(Q.size())
	{
		nod = Q.front();
		Q.pop();
		in[nod] = 0;
		for(vector<pereche>::iterator it = G[nod].begin();it!=G[nod].end();++it)
		if(it->cost + D[nod] < D[it->nod])
		{
			D[it->nod] = it->cost + D[nod];
			if(!in[it->nod])
				if(viz[it->nod] > N)
				{ciclu_negativ = 1;return;}
				else 
				{
					Q.push(it->nod);
					in[it->nod] = 1;
					++viz[it->nod];
				}
		}
		
	}
}
int main()
{
	read();
	bellmanford();
	ofstream g("bellmanford.out");
	int i;
	if(ciclu_negativ)
		g<<"-1\n";
	else
		for(i=2;i<=N;++i)
			g<<D[i]<<" ";
	g.close();
	return 0;
}