#include <iostream>
#include <fstream>
#include <queue>   
#include <vector>
#include <stdio.h>

#define INF 0x7fffffff
#define NMAX 50002

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct Nod {
    int nod;
    int distanta;
	bool operator<(const Nod &o) const
	{
		return distanta < o.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() {
	FILE * pFile;

	pFile = fopen("dijkstra.in", "r");
    //f >> n >> m;
	fscanf(pFile, "%d %d", &n, &m);
    while (m) {
        int x = 0, y = 0, dist = 0;
        //f >> x >> y >> dist;
		//FILE * pFile;

		//pFile = fopen("dijkstra.in", "r");
		fscanf(pFile, "%d %d %d", &x, &y, &dist);
        Nod nod_pereche;
        nod_pereche.nod = y;
        nod_pereche.distanta = dist;
        G[x].push_back(nod_pereche);
		m--;
    }
}
void solve() {
	priority_queue<Nod> setNoduri;
	/*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.push(new_nod);
	while (!setNoduri.empty()) {
		int nod = setNoduri.top().nod;
		int distanta = setNoduri.top().distanta;
		setNoduri.pop();
		
		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) {
					priority_queue<Nod> secondQueue;
					while (!setNoduri.empty()) {
						if (setNoduri.top().nod != to) {
							secondQueue.push(setNoduri.top());
						}
						setNoduri.pop();
					}
					setNoduri.swap(secondQueue);
				}
				dist[to] = dist_to + dist[nod];
				Nod new_nod_1;
				new_nod_1.nod = to;
				new_nod_1.distanta = dist[to];

				setNoduri.push(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;
}