//Bellman Ford cu coada!
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
#define INF 0x3f3f3f3f
#define SIZE 50005
#define mp make_pair
#define pb push_back
using namespace std;

int N, M, dmin[SIZE];
vector< pair<int, int> > graf[SIZE];
int main()
{
	int i, x, y, c;
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	
	scanf("%d%d", &N, &M);
	for(i = 0; i < M; scanf("%d%d%d", &x, &y, &c), graf[x].pb(mp(y, c)), i++);
	
	bool viz[SIZE];
	queue<int> Q;

	memset(dmin, INF, sizeof(dmin));
	memset(viz, false, sizeof(viz));
	
	dmin[1] = 0;
	Q.push(1);
	viz[1] = true;
	while(!Q.empty())
	{
	int nod = Q.front();
	Q.pop();
	viz[nod] = false;
	for(vector< pair<int, int> >::iterator it = graf[nod].begin(); it != graf[nod].end(); ++it)
	{
		if(dmin[nod] + it->second < dmin[it->first])
			{
				dmin[it->first] = dmin[nod] + it->second;
				if(!viz[it->first])
				{
					Q.push(it->first);
					viz[it->first] = true;
				}
			}
	}
	}
	
	for(i = 2; i <= N; i++)
		printf("%d ", dmin[i] < INF ? dmin[i] : 0);
	fclose(stdin);
	fclose(stdout);
}