#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>
#define NMAX 50010
#define INF 10000000

using namespace std;

int N, M;

vector < pair <int, int> > G[NMAX];
priority_queue < pair <int, int>, vector < pair<int,int> >, greater <pair <int, int> > > PQ;
int D[NMAX];

void Dijkstra(int nod){
	int i;
	for(i = 1; i <= N; i++)
		D[i] = INF;

	D[nod] = 0;

	PQ.push(make_pair(D[nod], nod));

	while(!PQ.empty()){

		pair <int, int> now;
		now = PQ.top();
		PQ.pop();

		vector < pair <int, int> > :: iterator it;
		for(it = G[now.second].begin(); it != G[now.second].end(); it++){
			if(D[(*it).second] > D[now.second] + (*it).first) {
				D[(*it).second] = D[now.second] + (*it).first;
				PQ.push(make_pair(D[(*it).second], (*it).second));
			}
		}

	}


}

int main(){
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	cin >> N >> M;
	int a, b, c;

	while(M--){
		cin >> a >> b >> c;
		G[a].push_back(make_pair(c, b));
	}


	Dijkstra(1);


	for(int i = 1; i <= N; i++)
		cout << D[i] << " ";

	cout << "\n";

	return 0;
}