#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 searchInHeap(int number) {
		int length = heapVector.size();
		for (int i = 0; i < length; ++i)
			if (heapVector[i] == number)
				return i;
		return -1;
	}
	int heapTop() {
		return heapVector[0];
	}	
	void siftUp() {
		bool modified = false;
		do {
			modified = false;
			int i, length = heapVector.size();
			for (i = length - 1; i > 0;) {
				if (heapVector[(i - 1) / 2] > heapVector[i]) {
					swap(heapVector[(i - 1) / 2], heapVector[i]);
					i = (i - 1) / 2;
					modified = true;
				}
				else break;
			}
		} while (modified);
	}
	void siftDown() {
		bool modified = false;
		do {
			modified = false;
			int i, length = heapVector.size();
			for (i = 0; i < length;) {
				if (2 * i + 1 < length && heapVector[2 * i + 1] < heapVector[i]) {
					swap(heapVector[2 * i + 1], heapVector[i]);
					modified = true;
					++i;
				}
				else {
					if (2 * i + 2 < length && heapVector[2 * i + 2] < heapVector[i]) {
						swap(heapVector[2 * i + 2], heapVector[i]);
						modified = true;
						i += 2;
					}
					else break;
				}
			}
		} while (modified);
	}
	void deleteHeapTop() {
		swap(heapVector[0], heapVector[heapVector.size() - 1]);
		heapVector.pop_back();
		siftDown();
	}
	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;
					int position = searchInHeap(arches[node - 1][i].first);
					siftUp();
				}	
			}
		}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;
}