#include <fstream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
int n, m, l;
vector<pair<int, int>> v[50001];
int dist[50001];
int use[50001];
struct comp
{
	bool operator()(int a, int b)
	{
		return dist[a] > dist[b];
	}
};

priority_queue<int, vector<int>, comp> q;
void calc(int src)
{
	for (int i = 1; i <= n; i++)
	{
		dist[i] = 10000000;
		use[i] = 0;
	}
	dist[src] = 0;
	q.push(src);
	use[src] = 1;
	int c;
	while (!q.empty())
	{
		c = q.top();
		q.pop();
		use[c] = 0;
		for (int i = 0; i < v[c].size(); i++)
		{
			if (dist[c] + v[c][i].second < dist[v[c][i].first])
			{
				dist[v[c][i].first] = dist[c] + v[c][i].second;
				if (use[v[c][i].first] == 0)
				{
					q.push(v[c][i].first);
					use[v[c][i].first] = 1;
				}
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	int x, y, c;
	for (int i = 1; i <= m; i++)
	{
		cin >> x >> y >> c;
		v[x].push_back({ y,c });
		//v[y].push_back({ x,c });
	}
	calc(1);
	for (int i = 2; i <= n; i++)
	{
		cout << dist[i] << " ";
	}
	return 0;
}