//#include "pch.h"
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <queue>
#include <bitset> 

using namespace std;

int MAX = 1 << 30;

vector<pair<int,int>> graph[50001];
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> prQueue;
bitset<50001> searched;
int distanceValues[50001];


int main()
{
	int n, m, x, y, cost;

	int startNode = 1;

	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");

	f >> n >> m;

	for (int i = 1; i <= n; ++i) {
		distanceValues[i] = MAX;
	}

	while (m--) {
		f >> x >> y >> cost;

		graph[x].push_back(make_pair(cost, y));
	}

	prQueue.push(make_pair(0,startNode));

	distanceValues[startNode] = 0;

	while (prQueue.size() > 0) {
		int node = prQueue.top().second;
		prQueue.pop();

		searched[node] = 1;

		for (pair<int, int> x : graph[node])
		{
			if (searched[x.second] == 1)continue;

			if ((distanceValues[node] + x.first) < distanceValues[x.second]) {
				distanceValues[x.second] = distanceValues[node] + x.first;
			}

			prQueue.push(make_pair(distanceValues[x.second],x.second));
		}
	}

	for (int i = 2; i <= n; ++i) {
		if(distanceValues[i]!=MAX)
		g << distanceValues[i] << " ";
		else g << 0 << " ";
	}
}