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

using namespace std;

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

		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;
		
		int start_node = 0;
		pq.push(make_tuple(0, start_node));
		

		while (!pq.empty())
		{
			tuple<int, int> mn;
			mn = pq.top();
			start_node = get<1>(mn);
			pq.pop();
			

			for (unsigned int i = 0; i < adj_list[start_node].size(); i++)
			{
				int dist, node;
				node = get<0>(adj_list[start_node][i]);
				dist = get<1>(adj_list[start_node][i]);
				
				if (!visited[node])
				{
					//tuple: first = distance, second = to that node
					pq.push(make_tuple(get<1>(adj_list[start_node][i]), get<0>(adj_list[start_node][i])));
					
					if (distances[node] > distances[start_node] + dist)
					{
						distances[node] = distances[start_node] + dist;
					}

				}
				
			}
			
			visited[start_node] = true;
			

		}

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




int main()
{

	Graph graph;

	graph.dijkstra();
	


	return 0;
}