#include <fstream>

#define MARE 100000000

using namespace std;

ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");

int a[1500][1500], sel[1500], d[1500], i, m, n, l, c, cost, s, nc;

void dijkstra (int s) {
	int min, dn, jmin, j;

	for (i = 1; i <= n; i++)
		d[i]=a[s][i];     // Initializam distanta fata de sursa.
	sel[s]=1; // Aratam ca sursa este selectata.
	d[s] = 0;   // Distanta de la sursa la sursa este 0.
	for (i = 2; i <= n; i++) {
		min = MARE;
		for (j=1 ; j<=n ; j++) // pentru fiecare nod
			if ( !sel[j])           // daca nu este selectat
				if (d[j]<min) {    // daca avem o valoare mai mica pentru distanta
				min=d[j]	;        // actualizam min
				jmin=j	;          // retinem nodul care ne da minimul [jmin]
				}
		sel[jmin] = 1 ; // Includem nodul jmin in multimea nodurilor selectate.
		for (j=1;j<=n;j++)     // Pentru fiecare nod_
			if (!sel[j]) {             // neselectat
			dn = d[jmin] + a[jmin][j]	; // Calculam distanta noua, folosind jmin.
				if (dn<d[j])          // Daca am gasit un lant mai scurt prin jmin,
					d[j]= dn;             // actualizam distanta de la sursa la nod.
			}
	}
}

int main () {
	fi >> n >> m;
	for (l = 1; l <= n; l++)
		for (c = 1; c <= n; c++)
			a[l][c] = MARE;
	for (i = 1; i <= m; i++) {
		fi >> l >> c; fi >> a[l][c];
	}
	dijkstra(1);
	for (i = 2; i <= n; i++) {
	  if(d[i]==MARE)
	  fo << "0"<< " ";
	  else
	  fo << d[i] << ' ';
//		for (nc = i; p[nc]; nc = p[nc])
//			cout << nc << " - "; // prezentam lantul de la nodul curent la sursa
//		cout << s << endl;
	}
}