#include <iostream>
#include <queue>
#include <vector>
#include <set>
#include <fstream>
#include <utility>
#include <numeric>

using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;


class Graph {
public:
	
	Graph(string f) {
		ifstream iff(f);
		iff >> N >> M;
		_g = vvii(N + 1, vii());

		for (int i = 0; i < M; ++i) {
			int A, B, C;
			iff >> A >> B >> C;
			_g[A].push_back(make_pair(B, C));
		}
	}

	vector<int> dijkstra() {
		set<ii> q;
		vector<int> d(N+1, numeric_limits<int>::max());
		q.insert(make_pair(1, 0));
		d[1] = 0;
		while (!q.empty()) {
			auto it = q.begin();
			int node = it->first;
			int val = it->second;
			
			q.erase(it);
			
			for (auto vecin : _g[node]) {

				int iv = vecin.first;
				int ival = vecin.second;
		
					
					
					int dist = d[node] + ival;

					if (d[iv] > dist) {
						
						if (d[iv] != numeric_limits<int>::max()) {
							q.erase(make_pair(iv, d[iv]));
						}

						d[iv] = dist;
						q.insert(make_pair(iv, dist));
					}
				
			}
		}
		return d;
	}

private:
	vector<vii> _g;
	int N, M;
};


int main() {
	Graph g("dijkstra.in");
	ofstream off("dijkstra.out");

	auto v = g.dijkstra();
	for (int i = 1; i < v.size(); ++i) {
		off << v[i] << " ";
	}

}