#include <fstream>
#include <queue>
#include <vector>
#include <bitset>
#include <algorithm>
#include <functional>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int nmax = 10000;
const int inf = 1000001;
int n, m, d[nmax];
vector<pair<int, int>> v[nmax];
priority_queue < pair<int,int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
bitset<nmax> viz;

void init(int s)
{
	for (int i = 1; i <= n; i++)
		d[i] = inf;
	d[s] = 0;
}

void dijkstra(int s)
{
	init(s);
	q.push(make_pair(d[s], s));
	while (!q.empty())
	{
		int x = q.top().second;
		q.pop();
		if (viz[x] = 1) continue;
		viz[x] = 1;
		for (int i = 0; i < v[x].size(); i++)
		{
			int y = v[x][i].first;
			int w = v[x][i].second;
			if (d[y]>d[x] + w)
			{
				d[y] = d[x] + w;
				//if (!viz[y])
					q.push(make_pair(d[y], y));
			}
		}
	}
}

int main()
{
	fin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y, z;
		fin >> x >> y >> z;
		v[x].push_back(make_pair(y, z));
	}
	dijkstra(1);
	for (int i = 2; i <= n; i++)
	{
		fout << d[i] << ' ';
	}
}