#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
#define INF 1<<30
priority_queue < pair <int, int>, vector< pair<int, int> >, greater< pair <int, int> >  > pq;
int n, m, d[50005], viz[50005];
vector < pair<int,int> > G[50005];
int main()
{
	freopen("dijkstra.in","r", stdin);
	freopen("dijkstra.out","w", stdout);
	
	int a,b,c;
	scanf("%d %d", &n, &m);
	for(int i=1; i<=m;i++)
	{
		scanf("%d %d %d", &a, &b, &c);
		G[a].push_back ( pair <int, int> (c,b) );
	}
	
	for(int i=2; i<=n; i++)
		d[i]=INF;
	d[1]=0;
	
	pq.push( pair<int, int> (0,1) );
	
	while( ! pq.empty() )
	{
		int u = pq.top().second;
		pq.pop();
		if(viz[u])	continue;
		
		viz[u]=true;		
		for(int i=0; i< G[u].size(); i++)
			if( d[ G[u][i].second ] > d[u] + G[u][i].first )
			{
				d[ G[u][i].second ] = d[u] + G[u][i].first;
				pq.push( pair <int, int> ( d[ G[u][i].second ] , G[u][i].second ) );
			}		
		
	}
	
	for(int i=2; i<=n;i++)
		printf("%d ", d[i]);	
	return 0;
}