#include<iostream>
#include<fstream>
using namespace std;

ifstream f("djikstra.in", ios::in);

struct drum{
	int nod;
	drum* next;
	int cost;
};

const int nmax = 50001;
int N, M;
drum* a[nmax];

void add(int x, int y, int z){
	drum *d = new drum();
	d->nod = y;
	d->cost = z;
	d->next = a[x];
	a[x] = d;
}


void citire(){
	f >> N >> M;
	int x, y, z;
	for (int i = 0; i <M; i++){
		f >> x >> y >> z;
		add(x, y, z);
	}
	f.close();
}

int d[nmax], q[nmax];
const long inf = 2 << 25;

void Djikstra(){
	d[1] = 0;
	for (int i = 2; i <= N; ++i){
		d[i] = inf;
	}

	int min,pmin = 0;

	for (int i = 1; i <= N; ++i){
		min = inf;
		for (int j = 1; j <= N; j++){
			if (d[j] < min && !q[j]){
				min = d[j];
				pmin = j;
			}
		}

		q[pmin] = 1;

		drum* t = a[pmin];

		while (t){
			if (t->cost + d[pmin] < d[t->nod])
				d[t->nod] = t->cost + d[pmin];

			t = t->next;
		}


	}

}



int main(){
	citire();
	Djikstra();

	ofstream g("djikstra.out", ios::out);

	for (int i = 2; i <= N; i++)
		g << d[i] << " ";

	g.close();
	return 0;
}