#include<stdio.h>
#include<set>
#include<vector>
#define mkp make_pair
#define pb push_back
using namespace std;

const int maxn = 60010;
const int INF = 1000000000;
int N,M;
vector<pair<int,int> > VECT[maxn];
int DIST[maxn];
set <pair<int,int> > S;


int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d %d",&N,&M);
	for(int i = 1;i <= M; ++i)
	{
		int x,y,c;
		scanf("%d %d %d",&x,&y,&c);
		VECT[x].pb(mkp(y,c));
//		VECT[y].pb(mkp(x,c));
	}
	for(int i = 2;i <= N; ++i) DIST[i] = INF;
	for(int i = 1;i <= N; ++i) S.insert(mkp(DIST[i],i));
	while(!S.empty())
	{
		set <pair <int,int> > :: iterator it = S.begin();
		int nod = (*it).second;
		S.erase(S.begin());
		for(unsigned int j = 0;j < VECT[nod].size(); ++j)
		{
			int vec = VECT[nod][j].first;
			int cost = VECT[nod][j].second;
			if (DIST[vec] > DIST[nod] + cost)
			{
				S.erase(S.find(mkp(DIST[vec],vec)));
				DIST[vec] = DIST[nod] + cost;
				S.insert(mkp(DIST[vec],vec));
			} 
		}
	}
	for(int i = 2;i <= N; ++i) if (DIST[i] == INF) DIST[i] = 0;
	for(int i = 2;i <= N; ++i) printf("%d ",DIST[i]);

	return 0;
}