#include<stdio.h>
#include<vector>
#include<queue>
#include<climits>

using namespace std;

int n, m, x, y, c;
vector< vector <pair<int,int> > > adiacente(50001);
vector<bool> vizitat(50001);
vector<int> dij(50001, INT_MAX);

struct cmp {
	bool operator() (const int &x, const int &y) {
		return dij[x] > dij[y];
	}
};

priority_queue<int,vector<int>,cmp> Q;

int main() {
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);

	scanf("%d %d", &n, &m);

	for (int i = 0; i < m; i ++) {
		scanf("%d %d %d", &x, &y, &c);
		adiacente[x].push_back(make_pair(y, c));
	}

	
	dij[1] = 0;
	Q.push(1);

	while (!Q.empty()) {
		x = Q.top();
		for (int i = 0; i < adiacente[x].size(); i ++)
			if (dij[x] + adiacente[x][i].second < dij[adiacente[x][i].first]) {
					dij[adiacente[x][i].first] = dij[x] + adiacente[x][i].second;
					Q.push(adiacente[x][i].first);
				}
		Q.pop();
	}

	for (int i = 2; i <= n; i ++)
		if (dij[i] == INT_MAX)
			printf("0 ");
			else printf("%d ", dij[i]);

	return 0;
}