#include <iostream>
#include <queue>
#include <vector>
#include <fstream>
#include <cstring>
#define NMAX 50010
using namespace std;
 
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

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){
	memset(D,0x3f,sizeof(D));

	D[nod] = 0;

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

	while(!PQ.empty()){

		pair <int, int> now;
		now = PQ.top();
		PQ.pop();
		if(D[now.second] == now.first) {
			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(){
	in >> N >> M;
	int a, b, c;

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

	Dijkstra(1);

	for(int i = 2; i <= N; i++)
		if(D[i] != 0x3f3f3f3f)
			out << D[i] << " ";
		else
			out << 0 << " ";

	return 0;
}