#include <fstream>
#include <vector>
#include <queue>

#define NMax 50010
#define INF 1000000000

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int nodes, edges, dist[NMax];
vector< pair<int, int> > G[NMax];
bool mark[NMax];

class cmp {
public:
	bool operator() (pair<int, int> d1, pair<int, int> d2)
	{
		return d1.second > d2.second;
	}
};

priority_queue< pair<int, int>, vector < pair<int, int> >, cmp > H;

void dijkstra(int source)
{
	mark[source] = 1;
	H.push(make_pair(source, 0));

	for (int i = 1; i <= nodes; i++)
		dist[i] = INF;
	dist[source] = 0;

	while (!H.empty()) {
		while (!H.empty() && mark[H.top().first])
			H.pop();
		if (H.empty())
			break;

		int crtNode = H.top().first;
		H.pop();

		mark[crtNode] = true;

		for (vector< pair<int, int> >::iterator it = G[crtNode].begin(); it != G[crtNode].end(); it++) {
			if (!mark[it->first]) {
				if (dist[it->first] > dist[crtNode] + it->second) {
					dist[it->first] = dist[crtNode] + it->second;
					H.push(make_pair(it->first, dist[it->first]));
				}
			}
		}
	}
}

int main()
{
	f >> nodes >> edges;

	int n1, n2, c;
	for (int i = 1; i <= edges; i++) {
		f >> n1 >> n2 >> c;

		G[n1].push_back(make_pair(n2, c));
	}

	dijkstra(1);

	for (int i = 2; i <= nodes; i++) {
		if (dist[i] != INF)
			g << dist[i] << " ";
		else
			g << 0 << " ";
	}
}