#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int,int> ii;
const int inf=1<<30;
vector<int> dist;
#define ECH(it,A)	for (typeof((A).begin()) it=(A).begin(); it!=(A).end(); ++it)
template <class T> void pvec(vector<T> &vec) { ECH(it,vec) cout << *it << ' '; cout << '\n'; }

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

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-1].push_back(ii(v2-1,weight));
	}
	vector<int> heap(2*n+1), pos(n+1);
	for (int i=0; i<n; ++i) {
		heap[i]=i;
		pos[i]=i;
	}
	for (int i=n; i<=2*n; ++i) heap[i]=n;
	dist.assign(n+1,inf);
	dist[0]=0;
	vector<ii>::iterator it;
	while (dist[heap[0]]!=inf) {
		//cout << heap[0] << '\n';
		for (it=adjlist[heap[0]].begin(); it!=adjlist[heap[0]].end(); ++it) {
			int v=it->first;
			dist[v]=min(dist[v], dist[heap[0]]+it->second);
			while (!cmp( v, heap[ (pos[v]-1)>>1 ] )) {
				int temp=heap[(pos[v]-1)>>1];
				swap( heap[ pos[v] ], heap[ (pos[v]-1)>>1 ] );
				swap( pos[v], pos[temp] );
			}
		}
		//pvec(heap);
		//cin.get();
		int del=0, temp;
		heap[0]=n;
		while (min(dist[heap[2*del+1]], dist[heap[2*del+2]])<inf) {
			if (cmp(heap[2*del+1], heap[2*del+2])) temp=2*del+2;
			else temp=2*del+1;
			//cout << del << ' ' << heap[del] << '\n';
			//cout << temp << ' ' << heap[temp] << '\n';
			//cin.get();
			swap( heap[del], heap[temp] );
			pos[heap[del]]=del;
			del=temp;
		}
	}
	//pvec(heap);
	//for (int i=0; i<n; i++) {
		//cout << dist[heap[i]] << ' ';
	//}
	//cout << '\n';
	for (int i=1; i<n; ++i) fout << (dist[i]==inf ?0 :dist[i]) << ' ';
	return 0;
}