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

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct Node{
		unsigned short node;
		unsigned short cost;
};
const int N_MAX = 5e4;
const int COST_MAX = 2e4;
vector<Node> edge[N_MAX];
int dist[N_MAX]{};
bool wasProcessed[N_MAX];


struct HeapCmp{
		bool operator()(unsigned short a, unsigned short b) const{
			return dist[a] > dist[b];
		}
};


void Dijkstra(unsigned short start){
	for(int i = 0; i < N_MAX; ++i)
		dist[i] = N_MAX * COST_MAX + 1, wasProcessed[i] = false;

	priority_queue<unsigned short, vector<unsigned short>, HeapCmp> heap;

	heap.push(start);
	dist[start] = 0;

	while(!heap.empty()){
		int node = heap.top();
		heap.pop();

		if(!wasProcessed[node]){
			wasProcessed[node] = true;

			for(auto neighbour: edge[node])
				if(dist[neighbour.node] > dist[node] + neighbour.cost){
					dist[neighbour.node] = dist[node] + neighbour.cost;
					heap.push(neighbour.node);
				}

		}
	}

	for(int i = 0; i < N_MAX; ++i)
		if(dist[i] == N_MAX * COST_MAX + 1)
			dist[i] = 0;
}

int main(){
	int nodes, edges, u, v, w;
	fin >> nodes >> edges;
	for(int i = 0; i < edges; ++i){
		fin >> u >> v >> w;
		--u, --v;

		edge[u].push_back({v, w});
	}

	Dijkstra(0);

	for(int i = 1; i < nodes; ++i)
		fout << dist[i] << ' ';
	fout.put('\n');

	fin.close();
	fout.close();
	return 0;
}