#include <iostream>
#include <fstream>
#include <set>
#include <vector>

#define INF 0x7fffffff
#define NMAX 50002

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct Nod {
    int nod;
    int distanta;
};
vector < vector < Nod > > G(NMAX);
vector < int > dist(NMAX, INF);
int n, m;

bool compare (const Nod& a, const Nod& b) {
    return a.distanta < b.distanta;
}

void read() {
    f >> n >> m;
    while (m--) {
        int x = 0, y = 0, dist = 0;
        f >> x >> y >> dist;
        Nod nod_pereche;
        nod_pereche.nod = y;
        nod_pereche.distanta = dist;
        G[x].push_back(nod_pereche);
    }
}
void solve() {
	set<Nod, bool(*)(const Nod& a, const Nod& b)> setNoduri(compare);
	/*for (int i = 2; i <= n; i++) {
		Nod new_nod;
		new_nod.nod = i;
		new_nod.distanta = INF;

		setNoduri.insert(new_nod);
	}*/
	Nod new_nod;
	new_nod.nod = 1;
	new_nod.distanta = 0;
	dist[1] = 0;
	setNoduri.insert(new_nod);
	while (!setNoduri.empty()) {
		int nod = (*setNoduri.begin()).nod;
		int distanta = setNoduri.begin()->distanta;
		setNoduri.erase(*setNoduri.begin());

		for (int i = 0; i < G[nod].size(); i++) {
			int to = G[nod][i].nod;
			int dist_to = G[nod][i].distanta;
			if (dist_to + dist[nod] < dist[to]) {
				

				if (dist[to] != INF) {
					for (set<Nod>::iterator it = setNoduri.begin(); it != setNoduri.end(); it++) {
						if (it->nod == to) {
							setNoduri.erase(it);
							break;
						}
					}
				}
				dist[to] = dist_to + dist[nod];
				Nod new_nod_1;
				new_nod_1.nod = to;
				new_nod_1.distanta = dist[to];

				setNoduri.insert(new_nod_1);
			}
		}
	}
	for (int i = 2; i <= n; i++) {
		if (dist[i] == INF) {
			g << "0 ";
		}
		else {
			g << dist[i] << " ";
		}
		
	}g << "\n";
}
int main()
{
    //set<Nod, bool(*)(const Nod& a, const Nod& b)> setNoduri(compare);
    read();
	solve();
	//cout << INF;
    /*std::copy(setNoduri.begin(), setNoduri.end(), std::ostream_iterator<Nod>(std::cout, "\n"));
    for (set<Nod>::iterator it = setNoduri.begin(); it != setNoduri.end(); it++) {
        cout << it->distanta <<" ";
    }*/
    return 0;
}