#include<fstream>
#include<set>
#include<vector>
#define Nmax 50007
#define INF 100000000
using namespace std;
vector< pair<int, int> > G[Nmax];
long n, m, i, j, viz[Nmax], nheap, d[Nmax];
struct heap {long ind, cost;};
heap aux;
set < pair<int,int> > S;
set< pair<int, int> > :: iterator it;
void dijkstra()
{
	heap aux2;
	while(!S.empty())
	{
		it = S.begin();
		aux.cost= (*it).first;
		aux.ind = (*it).second;
		viz[aux.ind]=1;
		S.erase( make_pair(aux.cost, aux.ind));
		for(i=0;i<G[aux.ind].size();i++)
			if(!viz[G[aux.ind][i].first] && d[G[aux.ind][i].first]>aux.cost+G[aux.ind][i].second)
			{
				d[G[aux.ind][i].first]=aux.cost+G[aux.ind][i].second;
				aux2.ind=G[aux.ind][i].first;
				aux2.cost=d[G[aux.ind][i].first];
				S.insert( make_pair(aux2.cost, aux2.ind));
			}
	}
}

int main()
{
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for(i=1;i<=m;i++)
	{
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		G[a].push_back(make_pair(b, c));
	}
	viz[1]=1;
	for(i=0;i<G[1].size();i++)
	{
		aux.ind=G[1][i].first;
		aux.cost=G[1][i].second;
		d[G[1][i].first]=aux.cost;
		S.insert(make_pair(aux.cost, aux.ind));
	}
	for(i=1;i<=n;i++)
		if(d[i]==0)
			d[i]=INF;
	
	dijkstra();
	for(i=2;i<=n;i++)
		if(d[i]==INF)
			printf("0 ");
		else
			printf("%d ", d[i]);
	printf("\n");
	
	return 0;
}