#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stdlib.h>
#include <stdio.h>
using namespace std;

const int MAXN = 50005;
const int INF = 1000000;

int N, M;
vector< pair<int, int> > G[MAXN];//tin minte muchiiile si costul (practic vecinii si costurile -un fel de lista de vecini)
int Dmin[MAXN];//Distanta minima pana la un nod

void citeste() {
	ifstream fin("dijkstra.in");

	fin >> N >> M;
	for (int i = 0; i < M; ++i) {
		int a, b, c;

		fin >> a >> b >> c;
		G[a].push_back(make_pair(b, c));//vecinul lui a este b iar costul arcului (a,b) este c
	}
}

void dijkstra() {
	bool viz[MAXN];// tipul bool (prescurtarea de la boolean poate lua valoarea true sau false
				// este deci mai convenabil(din punct de vedere al memoriei folosite) sa folosim bool in de int(4 octeti)

	queue<int> Q;  //queue =coada
	int i;
for(i=0;i<=MAXN;i++)
{
                    Dmin[i]=INF;
                    viz[i]=false;
                    }



	Dmin[1] = 0;
	Q.push(1);// Q.push(x) adauga pe x in coada(strcutura de tip FIFO)
	viz[1] = true;

	while (!Q.empty()) {  //cat timp coada nu s-a golit
		int nod = Q.front(); //retinem in nod primul element din coada (care asteapta sa fie servit)
		Q.pop();           //eliminam primul element din  coada
		viz[nod] = false;
//vector< pair<int, int> >::iterator it   -NU VA SPERIATI
// it este un iterator folosit pentru a parcurge itemii din vector
// este la fel ca si o variabila numai ca ii spunem ca va parcurge valori de tipul vector< pair<int, int> >

		//reamintim ca in G[nod][] retinem vecinii lui nod impreuna cu costurile aferente distantei de la nod la vecin
		//it = G[nod].begin() iteratorul cu numele it va retine inceputul listei de vecini a nodului nod
		// G[nod].end() =capatul listei de vecini a lui nod
		for (vector< pair<int, int> >::iterator it = G[nod].begin(); it != G[nod].end(); ++it)
			if (Dmin[nod] + it->second < Dmin[it->first]) {
				Dmin[it->first] = Dmin[nod] + it->second;
				if (!viz[it->first]) {
					Q.push(it->first);
					viz[it->first] = true;
				}
			}
	}
}

void afisare() {
	ofstream fout("dijkstra.out");

	for (int i = 2; i <= N; ++i)
		fout << (Dmin[i] < INF ? Dmin[i] : 0) << " ";
}

int main() {
	citeste();
	dijkstra();
	afisare();
}