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

class Heap {
private:
	vector<int> heapVector;
	const int infinite = 20001;
	vector<int> distances;
public:
	Heap(int N) {
		for (int i = 0; i < N; ++i) {
			heapVector.push_back(i + 1);
			distances.push_back(infinite);
		}
		distances[0] = 0;
	}
	int heapTop() {
		return heapVector[0];
	}	
	void sift() {
		bool changed = false;
		do {
			changed = false;
			int length = heapVector.size();
			for (int i = length - 1; i > 0; --i)
				if (distances[heapVector[i] - 1] < distances[heapVector[(i - 1) / 2] - 1]) {
					swap(heapVector[i], heapVector[(i - 1) / 2]);
					changed = true;
					break;
				}
		} while (changed == true);
	}
	void deleteHeapTop() {
		int length = heapVector.size();
		swap(heapVector[0], heapVector[length - 1]);
		heapVector.pop_back();
		sift();
	}
	void dijkstra(vector<vector<pair<int, int>> >& arches) {
		 do {
			int node = heapTop();
			deleteHeapTop();
			int length = arches[node - 1].size();
			for (int i = 1; i < length; ++i) {
				int cost = distances[node - 1] + arches[node - 1][i].second;
				if (distances[arches[node - 1][i].first - 1] > cost) {
					distances[arches[node - 1][i].first - 1] = cost;
					sift();
				}	
			}
		}while (!heapVector.empty());
	}
	void displayDistances(vector<vector<pair<int, int>> >& arches) {
		ofstream fout("dijkstra.out");
		dijkstra(arches);
		int length = distances.size();
		for (int i = 1; i < length; ++i) {
			if (distances[i] == infinite)
				distances[i] = 0;
			fout << distances[i] << " ";
		}
	}
};

int main() {
	ifstream fin("dijkstra.in");
	int N, M;
	fin >> N >> M;
	pair<int, int> defaultPair = pair<int,int>(0, 0);
	vector<vector<pair<int, int>> > arches(N, vector<pair<int, int>>(1, defaultPair));
	int x, y, z;
	for (int i = 0; i < M; ++i) {
		fin >> x >> y >> z;
		pair<int, int> newPair = pair<int, int>(y, z);
		arches[x - 1].push_back(newPair);
	}
	Heap solution(N);
	solution.displayDistances(arches);
	return 0;
}