#include <fstream>
#include <queue>
#include <vector>
#define NMAX 50009
#define INF (1<<30)

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int N, M, S, d[NMAX], ante[NMAX];
int x, y, l;


struct muchie {
	int vecin;
	int lungime;
};

muchie aux;

vector<muchie> G[NMAX];

// este o structura de comparare 
// folosita pentru a ordona doua noduri dupa distantele fata de sursa
struct cmp{ 
	//acesta este un operator cum este "<" (x < y)
	//el o sa apelze functia operator(x, y)
	//el presupune ca x < y. si vrea sa stie DACA trebuie sa le INTERSCHIMBE
	// adica daca d[x] > d[y] ( este mai departat x decat y, "x > y") atunci le intershimb
	//pentru ca el vrea ca (x,y) sa devina( min(x,y), max(x,y) )
    bool operator()(int x, int y){   
    	return d[x] > d[y];   
    };
};


priority_queue<int, vector<int>, cmp> pq;

/*
	// exemplu
	d[1] = 100;
	d[2] = 99;
	d[3] = 50;

	pq.push(1); // pq = {1} => top == 1
	pq.push(2); // pq = {2,1} => top == 2
	pq.push(3); // pq = {3, 2, 1} => top == 3

	// daca le extrag vor iesi in ordine, mai intai cele cu distanta mai mica
	while (!pq.empty()) {
		g << pq.top() << '\n';
		pq.pop();
	}
	// se afiseaza 3, 2, 1
*/


void dijkstra(int S) {
	// initializare
	for (int i = 1; i <= N; ++i) {
		// nu am ajuns inca de la S la i
		d[i] = INF; 
		ante[i] = 0;
	}

	// distana de la S la S
	d[S] = 0;
	ante[S] = 0;
	
	pq.push(S); // adaug sursa

	while (!pq.empty()) {
		int nod = pq.top(); // aleg nodul cel mai apropiat de S (din pq)
		pq.pop(); // elimin nodul

		// d[nod] este deja calculat optim, acum pot calcula(imbunatati) distantele si pentru vecini
		for (vector<muchie>::iterator it = G[nod].begin(); it != G[nod].end(); ++it) {
			// deci am muchi (x, y) de lungime l, unde: x = nod, y =  it->vecin, l = it->lungime
			if (d[nod] + it->lungime < d[it->vecin]) { // nod poate sa imbunatateasca distannta lui it->vecin
				d[it->vecin] = d[nod] + it->lungime; // actualizez lungimea
				ante[it->vecin] = nod; // actualizez tabloul pentru reconstituire

				// il bag pentru a imbunatati distantele vecinilor lui
				pq.push(it->vecin);
			}
		}

	}
}

 
void rebuild(int node,int S) {
    if(node == S) { 
      g<< S <<' '; 
      return; 
    }
     
    rebuild(ante[node], S);
     
    g<<node<<' ';
}

int main() {
	f >>  N >> M;

	for (int i = 1; i <= M; ++i) {
		f >> x >> y >> l;

		aux.vecin = y;
		aux.lungime = l;
		G[x].push_back(aux);

		/* daca era neorientat adaugam
		aux.vecin = x;
		aux.lungime = l;
		G[y].push_back(aux);
		*/
	}

	S = 1; // pe infoarena sursa este 1 :D
	dijkstra(S); // calculeaza toate distantele de la S la celelalte noduri si salveaza-le in d

	for (int i = 2; i <= N; ++i) {
		if (d[i] != INF) { // verific daca s-a ajuns de la S la i
			g << d[i] << ' '; 
		} else {
			g << 0 << ' ';
		}
	}
	f.close();
	g.close();
	return 0;
}