#include <stdio.h>
#include <queue>
#include <vector>

using namespace std;

#define MN (50000)
#define INF (50000001) // MN*1000+1 with 1000 being the maximum cost of an edge

vector<int> g[MN]; // graph
vector<int> c[MN]; // cost
int d[MN]; // distance
int N; // number of nodes
int M; // number of edges

class cmp {
public:
	bool operator()(const pair<int, int> &n1, const pair<int, int> &n2)
	{
		return n1.second > n2.second;
	}
};

priority_queue< pair<int, int>, vector< pair<int, int> >, cmp> q; // node, distance

void dijkstra(int startNode)
{
	int i, n1, n2, n1d;
	for(i = 0; i < N; ++i)
		d[i] = INF;
	q.push(make_pair(startNode, d[startNode] = 0));
	while(!q.empty()) {
		n1 = q.top().first;
		n1d = q.top().second;
		q.pop();
		if(n1d > d[n1])
			continue;
		//printf("Using %d with %d\n", n1, n1d);
		for(i = 0; i < g[n1].size(); ++i) {
			n2 = g[n1][i];
			if(d[n1]+c[n1][i] < d[n2]) {
				d[n2] = d[n1]+c[n1][i];
				q.push(make_pair(n2, d[n2]));
			}
		}
	}
}

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

	scanf("%d %d", &N, &M);

	for(i = 0; i < M; ++i) {
		scanf("%d %d %d", &A, &B, &C); --A; --B;
		g[A].push_back(B);
		c[A].push_back(C);
	}

	dijkstra(0);

	for(i = 1; i < N; ++i)
		printf("%d ", d[i] == INF? 0 : d[i]);

	return 0;
}