#include<cstdio>
#include<vector>
#include<queue>
#define inf 999999
#define max 50010
using namespace std;

/*
	reprezint graful prin liste de adiacenta cu costuri
	first - extremitatea finala
	second -costul
*/
vector< pair <int, int> > graf[max];

/*
	dmin - vector care contine distantele de la sursa la fiecare nod
	pre - vector care reconstituie drumul
*/
int dmin[max], pre[max];

/*
	Functor pentru coada cu prioritati
*/
class Compara
{
public:
	
	bool operator() (const int&x, const int& y){
		return dmin[x] > dmin[y];
	}
	
};

/*
	Coada cu prioritati
	organizeaza elementele intr-un min-heap
	la fiecare pas sa putem extrage elementul pentru care dmin e minim
*/
priority_queue<int, vector<int>, Compara> coada;

/*
	nrv - numarul de varfuri
	x0 - varsul de start
	nrm - numarul de muchii
*/
int nrv, x0 = 1, nrm;

void citire();
void dijkstra();
void afisare();

int main(){
	
	citire();
	dijkstra();
	afisare();
	return 0;
}

void citire(){

	int x, y, c;

	FILE* f = fopen("dijkstra.in", "r");
	fscanf(f, "%d%d", &nrv, &nrm);
	
	for(int i = 1; i <= nrm; i++){
		fscanf(f, "%d%d%d", &x, &y, &c);
		graf[x].push_back(make_pair(y, c));
	}
	fclose(f);
}

void dijkstra(){

	int vfmin;

	for(int i = 1; i <= nrv; i++){
		dmin[i] = inf;
		pre[i] = x0;
	}
	dmin[x0] = 0;
	pre[x0] = 0;

	coada.push(x0);
	while(!coada.empty()){
		vfmin = coada.top();
		coada.pop();
		for(int i = 0; i < graf[vfmin].size(); i++){
			if(dmin[graf[vfmin][i].first] > dmin[vfmin] + graf[vfmin][i].second){
				dmin[graf[vfmin][i].first] = dmin[vfmin] + graf[vfmin][i].second;
				pre[graf[vfmin][i].first] = vfmin;
				coada.push(graf[vfmin][i].first);
			}
		}

	}

}

void afisare(){
	FILE* g = fopen("dijkstra.out", "w");

	for(int i = 2; i <= nrv; i++)
		if(dmin[i] != inf)
			fprintf(g, "%d ", dmin[i]);
		else
			fprintf(g, "0 ");

	fclose(g);
}