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

#define DEBUG 0

#if DEBUG==1
#define out cout
#endif

typedef pair<int, int> edge;

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

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

	// Read from file
	ifstream in ("dijkstra.in");
#if DEBUG == 0
	ofstream out ("dijkstra.out");
#endif
	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())
	{
#if DEBUG==1
		cout<<"Dist: ";
		for (int i=1; i<=N; i++)
		{
			if (dist[i] == INF) cout<<"x ";
			else cout<<dist[i]<<" ";
		}
		cout<<"\n";
#endif

		int c = unvisited.top().first, x = unvisited.top().second;
		unvisited.pop();

		if (visited[x]) continue;
		visited[x] = true;

		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;
}