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

#define NMax 50010
#define INF 2000000000

using namespace std;

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

int nodes, edges, distances[NMax];
bool mark[NMax];
vector< pair<int, int> > G[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;


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));
	}

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

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

	while (!H.empty()) {

		pair<int, int> node;
		node = H.top();
		H.pop();

		mark[node.first] = true;

		for (vector< pair<int, int> >::iterator it = G[node.first].begin(); it != G[node.first].end(); it++) {

			if (distances[node.first] + it->second < distances[it->first]) {
				distances[it->first] = distances[node.first] + it->second;
				H.push(make_pair(it->first, distances[it->first]));
			}
				
		}

	}

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

	return 0;
}