#include <fstream>
#include <vector>
#include <queue>
using namespace std;

vector<int> bellmanFord(vector<vector<pair<int, int>>>& adjacentLists, int N) {
	queue<int> bellmanQueue;
	bellmanQueue.push(1);
	vector<bool> inQueue(N, false);
	inQueue[0] = true;
	vector<int> distances(N, INT_MAX);
	distances[0] = 0;
	while (!bellmanQueue.empty()) {
		int currentNode = bellmanQueue.front();
		int length = adjacentLists[currentNode - 1].size();
		for (int i = 1; i < length; ++i) {
			int totalCost = distances[currentNode - 1] + adjacentLists[currentNode - 1][i].second;
			if (totalCost < distances[adjacentLists[currentNode - 1][i].first - 1]) {
				distances[adjacentLists[currentNode - 1][i].first - 1] = totalCost;
				bellmanQueue.push(adjacentLists[currentNode - 1][i].first);
			}
		}
		bellmanQueue.pop();
	}
	return distances;
}


int main() {
	ifstream fin("bellmanford.in"); 
	int N, M;
	fin >> N >> M;
	vector<vector<pair<int, int>>> adjacentLists(N, vector<pair<int, int>>(1, pair<int, int>(0, 0)));
	int start, destination, cost;
	for (int i = 0; i < M; ++i) {
		fin >> start >> destination >> cost;
		adjacentLists[start - 1].push_back(pair<int, int>(destination, cost));
	}
	vector<int> minimumDistance;
	minimumDistance = bellmanFord(adjacentLists, N);
	ofstream fout("bellmanford.out");
	for (int i = 1; i < N; ++i)
		fout << minimumDistance[i] << " ";
	return 0;
}