#include <bits/stdc++.h>
#define NMAX 50009
#define INF 999999999999LL
#define int long long int
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n, m;
vector< pair<int, int> >g[NMAX];
void citire();
void djk();
bool uz[NMAX];
int sol[NMAX];
class compar
{
public:
	bool operator ()(pair<int, int>a, pair<int, int> b)
	{
		return a.second > b.second;
	}
};
priority_queue <pair<int, int>, vector<pair<int, int> >, compar> H;
int32_t main()
{
	citire();
	djk();

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

	}

}
void djk()
{
	int i;
	for (i = 0; i < NMAX; i++)
		sol[i] = INF;
	sol[1] = 0;
	H.push(make_pair( 1,0 ));
	uz[1] = 1;
	while (!H.empty())
	{
		pair<int, int>act = H.top(); H.pop();
		//uz[act.first] = 0;

		for (i = 0; i < g[act.first].size(); i++)
		{
			int vec = g[act.first][i].first;
			int cost = g[act.first][i].second;
			if (sol[vec] > act.second + cost)
			{
				sol[vec] = act.second + cost;
				uz[vec] = 1;
				H.push( make_pair(vec,sol[vec] ));
				
			}
		}
	}
	for (i = 2; i <= n; i++)
		if (sol[i] == INF)
			fout << 0 << " ";
		else
			fout << sol[i] << " ";

}