#include<stdio.h>
#include<queue>
#include<vector>
#define INF 1<<30
using namespace std;

priority_queue < pair <int , int> , vector < pair <int , int> >, greater < pair< int , int> > > pq;
vector < pair <int,int> > G[50005];
int n, m, viz[50005], d[50005], a, b, c;

int main()
{
	freopen("dijkstra.in","r", stdin);
	freopen("dijkstra.out","w", stdout);

	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;

	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++)
        if(d[i]!=INF)
            printf("%d ", d[i]);
        else
            printf("%d ", 0);
	
	return 0;
}