#include <cstdio>
#include <set>
#include <vector>
using namespace std;

#define fiu vec[nod][i]

const int MAX_N = 50010;

vector <int> vec[MAX_N], cost[MAX_N];
int n, m;
int f[MAX_N];
set < pair <int, int> > a;

int main()
{
	int i, x, y, c;
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	
	scanf("%d %d", &n, &m);
	for (i = 0; i < m; ++i)
	{
		scanf("%d %d %d", &x, &y, &c);
		vec[x].push_back(y);
		cost[x].push_back(c);
	}

	memset(f, 0x3f3f3f3f, sizeof(f));
	f[1] = 0;

	a.insert(make_pair(0, 1));

	while (!a.empty())
	{
		int nod = (*a.begin()).second;
		a.erase(a.begin());

		for (i = 0; i < vec[nod].size(); ++i)
			if (f[fiu] > f[nod] + cost[nod][i])
			{
				f[fiu] = f[nod] + cost[nod][i];
				a.insert(make_pair(f[fiu], fiu));
			}
	}

	for (i = 2; i <= n; ++i) printf("%d\n", (f[i] == 0x3f3f3f3f) ? 0 : f[i]); 
}