#include <bits/stdc++.h>

#define dist first
#define nod second

using namespace std;

const int MAX_N = 50000;
const int INF = 1000000000;
vector<pair<int, int> > graph[1+MAX_N];

struct cmpd {
	bool operator() (pair<int, int> a, pair<int, int> b) {
		return a.first > b.first;
	}
};

priority_queue<pair<int, int>, vector<pair<int, int> >, cmpd> q;
int d[1+MAX_N];
bool viz[1+MAX_N];

int main() {
	int n, m, a, b, c;
	FILE *fin = fopen("dijkstra.in", "r");
	fscanf(fin, "%d%d", &n, &m);
	for(int i = 2; i <= n; ++i)
	  d[i] = INF;
	for(int i = 0; i < m; ++i) {
		fscanf(fin, "%d%d%d", &a, &b, &c);
		graph[a].push_back({b, c});
	}
	fclose(fin);

	q.push({0, 1});
	while(!q.empty()) {
		pair<int, int> t;
		t = q.top();
		q.pop();
		if(!viz[t.nod]) {
			viz[t.nod] = true;
			for(auto it: graph[t.nod])
				if(d[t.nod] + it.second < d[it.first]) {
					d[it.first] = d[t.nod] + it.second;
					q.push({d[it.first], it.first});	
				}
		}
	}

	FILE *fout = fopen("dijkstra.out", "w");
	for(int i = 2; i <= n; ++i) {
	  if(d[i] == INF)
		  d[i] = 0;
		fprintf(fout, "%d ", d[i]);
	}
	fclose(fout);
	return 0;
}