#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n, m;
int oo = (1 << 30);
int d[50005];
int f[50005];

vector<pair<int, int>> g[50005];

struct compara_dist
{
	bool operator() (int x, int y) {
		return	d[x] > d[y];
	}
};
priority_queue <int, vector<int>, compara_dist> coada;

void citire()
{
	int x, y, c;
	fin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		fin >> x >> y >> c;
		g[x].push_back(make_pair(y, c));
	}
}

void afisare()
{
	for (int i = 2; i <= n; i++)
	{
		if (d[i] != oo) fout << d[i] << ' ';
		else fout << 0 << ' ';
	}
}

void dijkstra(int start)
{
	for (int i = 1; i <= n; i++) d[i] = oo;
	d[start] = 0;
	coada.push(start);
	f[start] = 1;
	while (!coada.empty())
	{
		int k = coada.top();
		coada.pop();
		f[k] = 0;
		for (int i = 0; i < g[k].size(); i++)
		{
			int vecin = g[k][i].first;
			int cost = g[k][i].second;
			if (d[k] + cost < d[vecin]) {
				d[vecin] = d[k] + cost;
				if (f[vecin] == 0) {
					coada.push(vecin);
					f[vecin] = 1;
				}
			}
		}
	}
}

int main()
{
	citire();
	dijkstra(1);
	afisare();
}