#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int,int> ii;
const unsigned int inf=1<<30;
vector<unsigned int> dist, heap, pos;

inline bool cmp(int a, int b) {
	return dist[a]>=dist[b];
}

void heap_swap(int node1, int node2) {
	swap(pos[heap[node1]],pos[heap[node2]]);
	swap(heap[node1],heap[node2]);
}

int main() {
	ifstream fin("dijkstra.in");
	ofstream fout("dijkstra.out");
	int n, nedge;
	fin >> n >> nedge;
	vector<vector<ii> > adjlist(n+1);
	for (int i=0,v1,v2,weight; i<nedge; ++i) {
		fin >> v1 >> v2 >> weight;
		adjlist[v1].push_back(ii(v2,weight));
	}
	heap.resize(n+1), pos.resize(n+1);
	for (int i=1; i<=n; ++i) {
		heap[i]=i;
		pos[i]=i;
	}
	dist.assign(n+1,inf);
	dist[1]=0;
	vector<ii>::iterator it;
	while (dist[heap[1]]<inf) {
		for (it=adjlist[heap[1]].begin(); it!=adjlist[heap[1]].end(); ++it) {
			int v=it->first;
			if (pos[v]>=heap.size()) continue;
			dist[v]=min(dist[v], dist[heap[1]]+it->second);
			while (!cmp(v, heap[pos[v]>>1])) {
				heap_swap( pos[v], pos[v]>>1 );
			}
		}
		heap_swap(1,heap.size()-1);
		heap.pop_back();
		int temp, v=heap[1];
		while (true) {
			if (heap.size()<=2*pos[v]) break;
			if (heap.size()==2*pos[v]+1) temp=2*pos[v];
			else {
				if (cmp(heap[2*pos[v]], heap[2*pos[v]+1])) temp=2*pos[v]+1;
				else temp=2*pos[v];
			}
			if (cmp(heap[temp],v)) break;
			heap_swap(pos[v],temp);
		}
	}
	for (int i=2; i<=n; ++i) fout << (dist[i]==inf ?0 :dist[i]) << ' ';
	return 0;
}