#include <fstream>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
struct Edge{
	int src,dest,cost;
};
Edge edge[250000];
int n, m;
int dis[250000], IMAX = 9999999;

void Bellmanford(int src) {
	for (int i = 1; i <= n; i++)
		dis[i] = IMAX;
	dis[src] = 0;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {

			int s = edge[j].src;
			int d = edge[j].dest;
			int c = edge[j].cost;

			if (dis[s] != IMAX && dis[d] > dis[s] + c) {
				dis[d] = dis[s] + c;
			}
		}
	}
}
int main() {
	fin >> n;
	fin >> m;
	int x, y, z;
	for (int i = 1; i <= m; i++) {
		fin >> edge[i].src >> edge[i].dest >> edge[i].cost;
	}

	Bellmanford(1);
	for (int i = 2; i <= n; i++)
		fout << (dis[i]>=IMAX?0:dis[i]) << " ";
}