#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);
vector < bool > vizitat(NMAX, false);
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;
	priority_queue<int> qNod;
	/*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;
	qNod.push(1);
	while (!qNod.empty()) {
		int nod = qNod.top();
		qNod.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 (!vizitat[to]) {
					vizitat[to] = true;
					qNod.push(to);
				}
				dist[to] = dist_to + dist[nod];
				qNod.push(to);
			}
		}
	}
	FILE * pFile;

	pFile = fopen("dijkstra.out", "w");
	for (int i = 2; i <= n; i++) {
		if (dist[i] == INF) {
			dist[i] = 0;
		}
		fprintf(pFile, "%d ", dist[i]);
		
	}
}
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;
}