#include <fstream>
#include <vector>
#include <queue>
#define MAXN 50005
#define INF 0x7fffffff
using namespace std;

typedef pair<int, int> edge;

vector<int> edges[MAXN], cost[MAXN];
priority_queue <edge> unvisited;
int N, M, dist[MAXN];
int n, v;

int main()
{
	int from, to, c;

	// Read from file
	ifstream in ("dijkstra.in");
	ofstream out ("dijkstra.out");
	in>>N>>M;

	for (int i=0; i<M; i++)
	{
		in>>from>>to>>c;
		edges[from].push_back(to);
		cost[from].push_back(c);
	}

	// Initialize distance array
	dist[1] = 0;
	for (int i=2; i<=N; i++) dist[i] = INF;
	unvisited.push(make_pair(0, 1));

	// Calculate distances
	while (!unvisited.empty())
	{
		int c = unvisited.top().first, x = unvisited.top().second;
		unvisited.pop();

		for (int i = 0; i < edges[x].size(); i++)
			if (dist[edges[x][i]] > c + cost[x][i])
			{
				dist[edges[x][i]] = c + cost[x][i];
				unvisited.push(make_pair(dist[edges[x][i]], edges[x][i]));
			}
	}

	// Display distances
	for (int i=2; i<=N; i++)
		out<<dist[i]<<" ";

	in.close();
	return 0;
}