#include <fstream>
#include <vector>
#include <set>

using namespace std;

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

struct Node{
		unsigned short node;
		int 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] || (dist[a] == dist[b] && a < b);
		}
};


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

	set<unsigned short, HeapCmp> heap;

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

	while(!heap.empty()){
		int node = *heap.begin();
		heap.erase(heap.begin());

		wasProcessed[node] = true;

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

				auto it = heap.find(neighbour.node);
				if(it != heap.end())
					heap.erase(it);

				heap.insert(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;
}