#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#include <algorithm>
#include <stack>
#include <tuple>
#include <queue>

using namespace std;
# define INF 0x3f3f3f3f
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");


class Graph
{

public:

	Graph(){}
	~Graph(){}

	void dijkstra()
	{
		vector<vector<tuple<int, int>>> adj_list;
		vector<tuple<int, int>> empty;
		vector<bool> visited;
		vector<int> distances;
		
		//reading the values
		int N, E;
		fin >> N >> E;

		for (int i = 0; i < N; i++)
		{
			adj_list.push_back(empty);
			visited.push_back(false);
			distances.push_back(INF);
		}

		int edge1, edge2, cost;
		for (int i = 0; i < E; i++)
		{
			fin >> edge1 >> edge2 >> cost;
			edge1--;
			edge2--;
			adj_list[edge1].push_back(make_tuple(edge2, cost));
			//adj_list[edge2].push_back(make_tuple(edge1, cost));
		}

		//the algorithm
		priority_queue<tuple<int, int>, vector<tuple<int, int>>, greater<tuple<int, int>> > pq;
		distances[0] = 0;
		pq.push(make_tuple(0, 0));

		while (!pq.empty())
		{
			tuple<int, int> dist_node = pq.top();
			while (visited[get<1>(dist_node)])
			{
				pq.pop();
				dist_node = pq.top();
			}
			int node, dist;
			node = get<1>(dist_node);
			dist = get<1>(dist_node);
			pq.pop();
			visited[node] = true;

			for (tuple<int,int> neighbour : adj_list[node])
			{
				if (visited[get<0>(neighbour)])
				{
					continue;
				}

				int new_dist = distances[node] + get<1>(neighbour);

				if (new_dist < distances[get<0>(neighbour)])
				{
					distances[get<0>(neighbour)] = new_dist;
					pq.push(make_tuple(new_dist, get<0>(neighbour)));
				}
			}

		}
		

		for (unsigned int i = 1; i < distances.size(); i++)
		{
			if (distances[i] == INF)
			{
				fout << "0 ";
			}
			else
			{
				fout << distances[i] << " ";
			}
		}
	}
};




int main()
{

	Graph graph;

	graph.dijkstra();
	


	return 0;
}