#include <fstream>
#include <list>
#include <vector>
#include <queue>
#include <climits>
#include <bitset>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

class WeightedGraph {

public:
	int to, cost;
};

const int maxV = 50000;
const int Inf = INT_MAX;

list <WeightedGraph> adjList[1 + maxV];
vector <int> dist;
bitset <1 + maxV> inHeap;
int V, E;

void readData() {

	fin >> V >> E;

	for (; E; --E) {

		int from, to, cost;
		fin >> from >> to >> cost;

		adjList[from].push_back({ to, cost });
	}
}

void Dijkstra(int node) {

	dist.resize(1 + V);
	fill(dist.begin(), dist.end(), Inf);
	dist[node] = 0;

	priority_queue < pair <int, int>, vector < pair <int, int> >, greater < pair <int, int> > > Heap;
	Heap.push({ dist[node], node });
	inHeap[node] = true;

	while (!Heap.empty()) {

		node = Heap.top().second;
		Heap.pop();
		inHeap[node] = false;

		for (const WeightedGraph &edge : adjList[node]) {

			int nextNode = edge.to;
			int cost = edge.cost;

			if (dist[nextNode] > dist[node] + cost) {

				dist[nextNode] = dist[node] + cost;
				if (!inHeap[nextNode]) {

					Heap.push({ dist[nextNode], nextNode });
					inHeap[nextNode] = true;
				}
			}
		}
	}
}

int main() {

	readData();
	Dijkstra(1);

	for (int node = 2; node <= V; ++node)
		if (dist[node] == Inf)
			fout << 0 << ' ';
		else fout << dist[node] << ' ';
}