#include<fstream>
#include<cstring>
#include<vector>
#include<set>
#define N 50001
#define INF 1000000001
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

int* Dijkstra(vector<pair<int, int> > *v, int n)
{
	int *dist = new int[n + 1];
	memset(dist, INF, sizeof dist);

	set<pair<int, int> > heap;

	heap.insert(make_pair(0, 1));

	while(!heap.empty())
	{
		int node = heap.begin() -> second;
		int bestDist = heap.begin() -> first;
		heap.erase(heap.begin());

		for(int i = 0; i < v[node].size(); ++i)
		{
			int to = v[node][i].first;
			int cost = v[node][i].second;
			if(dist[to] > bestDist + cost)
			{
				if(dist[to] != INF)
				{
					heap.erase(make_pair(dist[to], to));
				}
				dist[to] = bestDist + cost;
				heap.insert(make_pair(dist[to], to));
			}
		}
	}

	return dist;
}

int main(){
	int n, m;
	cin >> n >> m;

	vector<pair<int, int> > v[n + 1];

	for(int i = 1; i <= m; ++i)
	{
		int from, to, cost;
		cin >> from >> to >> cost;
		v[from].push_back(make_pair(to, cost));
	}

	int *dist = Dijkstra(v, n);

	for(int i = 2; i <= n; ++i)
	{
		cout << dist[i] << " ";
	}
    cout << endl;
	cin.close();
	cout.close();
	return 0;
}