#include <iostream>

#include <fstream>

#include <vector>

#include <queue>



using namespace std;



#define MAXIM 100000



vector <int> graph[100005];

vector <int> graphC[100005];

priority_queue <pair<int, int> > myheap;

int viz[100005];

int dist[100005];



int main()

{

	ifstream f("dijkstra.in");

	ofstream g("dijkstra.out");

	int n, m;

	f >> n >> m;

	int a, b, c;

	for (int i = 1; i <= m; i++)

	{

		f >> a >> b >> c;

		graph[a].push_back(b);

		graphC[a].push_back(c);

	}

	dist[1] = 0;

	myheap.push(make_pair(0, 1));

	for (int i = 2; i <= n; i++)

	{

		dist[i] = MAXIM;

		myheap.push(make_pair(-dist[i], i));

	}

	while (!myheap.empty())

	{

		pair <int, int> best = myheap.top();

		myheap.pop();

		int index = best.second;

		if (viz[index])

			continue;

		viz[index] = 1;

		int lim = graph[index].size();

		for (int i = 0; i < lim; i++)

		{

			int vecin = graph[index][i];

			int cost = graphC[index][i];

			if (dist[index] + cost < dist[vecin])

			{

				dist[vecin] = dist[index] + cost;

				myheap.push(make_pair(-dist[vecin], vecin));

			}

		}

	}

	for (int i = 2; i <= n; i++)

		if (dist[i] == MAXIM)

			g << 0 << " ";

		else

			g << dist[i] << " ";

	return 0;

}