#include<fstream>
#include<vector>
#include<algorithm>
#define inf 60000000
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int m,i,D[50005],change,n;
struct el
{
	int s,d,c;
}v[250005];
int cm(el a,el b)
{
	if(a.s!=b.s)
	return a.s<b.s;
	else
		return a.d<b.d;
}
int main ()
{
	f>>n>>m;
	for(i=2;i<=n;++i)
		D[i]=inf;
	for(i=1;i<=m;++i)
	{
		f>>v[i].s>>v[i].d>>v[i].c;
		if(v[i].s==1)
			D[v[i].d]=v[i].c;
	}
	sort(v+1,v+m+1,cm);
	change=1;
	while(change)
	{
		change=0;
		for(i=1;i<=m;++i)
		{
			if(D[v[i].s]+v[i].c<D[v[i].d]&&D[v[i].s]!=inf)
			{
				D[v[i].d]=D[v[i].s]+v[i].c;
				change=1;
			}
		}
	}
	for(i=2;i<=n;++i)
		if(D[i]==inf)
		{
			g<<"-1";
			return 0;
		}
	for(i=2;i<=n;++i)
		g<<D[i]<<" ";
	return 0;
}