#include<set>
#include<fstream>
#include<vector>
#define MAX 50001
#define INF 0x3f3f3f
using namespace std;
vector<pair<int,int> > G[MAX];
multiset<pair<int,int> > S;
int N,M,D[MAX];
void dijkstra()
{
	vector<pair<int,int> >::iterator it;
	multiset<pair<int,int> >::iterator itS;
	S.insert(make_pair(1,0));
	int x,val,nod;
	while(!S.empty())
	{
		itS = S.begin();
		x = itS->first;
		val = itS->second;
		S.erase(itS);
		for(it = G[x].begin();it!=G[x].end();++it)
		{
			nod = it->first;
			if(D[nod] > val + it->second)
			{
				if(D[nod] != INF)
					S.erase(make_pair(nod, D[nod]));
				D[nod] = val + it->second;
				S.insert(make_pair(nod, D[nod]));
			}
		}
	}
	
}
int main()
{
	ifstream f("fisier.in");
	f>>N>>M;
	int x,y,c,i;
	for(x=1;x<=N;++x)
		D[x] = INF;
	D[1] = 0;
	
	while(M--)
	{
		f>>x>>y>>c;
		G[x].push_back(make_pair(y,c));
	}
	f.close();
	dijkstra();
	ofstream g("fisier.out");
	for(i=2;i<=N;++i)
	{
		if(D[i] == INF)D[i] = -1;
		g<<D[i]<<" ";
	}
	g.close();
	return 0;
}