#include <fstream>
#include <vector>
#include <utility>
#include <algorithm>
#include <deque>

#define mp make_pair
#define ff first
#define ss second
#define BIG 2000000000


using namespace std;

int dist[50001];
pair<int,int> frontier[250001],temp,ty;
vector < pair <int,int> > v[50001];


inline int leftChild(int x) {
	return frontier[2*x].ff;
}

inline int rightChild(int x) {
	return frontier[2*x+1].ff;
}

pair <int,int> getHeap() {
	pair <int,int> x=frontier[1];
	int in=1;
	frontier[1]=frontier[frontier[0].ff];
	frontier[0].ff--;
	while ((frontier[in].ff>leftChild(in)||frontier[in].ff>rightChild(in) )&&(2*in<=frontier[0].ff)) {
		if (leftChild(in)<rightChild(in)) {
			swap(frontier[in],frontier[2*in]);
			in*=2;
		}
		else if (2*in+1<=frontier[0].ff) {
			swap(frontier[in],frontier[2*in+1]);
			in=2*in+1;
		}
	}
	
	return x;	
}

void insertHeap(pair <int,int> x) {
	frontier[++frontier[0].ff]=x;
	int in = frontier[0].ff;
	while (in!=1&&frontier[in].ff<frontier[in/2].ff) {
		swap(frontier[in],frontier[in/2]);
		in/=2;
	}	
}

int main() {	
	int ori,i,n,m;
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	
	f>>n>>m;
	
	for (i=1; i<=m; i++) {
		f>>ori>>temp.ss>>temp.ff;
		v[ori].push_back(temp);
	}
	
	for (i=2; i<=n; i++)
		dist[i]= BIG;
	

		insertHeap(mp(0,1));
	
	while (frontier[0].ff) {
		temp=getHeap();
		for (i=0; i<v[temp.ss].size(); i++) 
			if (dist[temp.ss]+v[temp.ss][i].ff<dist[v[temp.ss][i].ss]) {
				dist[v[temp.ss][i].ss]=dist[temp.ss]+v[temp.ss][i].ff;
				ty.ff=dist[v[temp.ss][i].ss];
				ty.ss=v[temp.ss][i].ss;
				insertHeap(ty);
			}
			
	}
	
	for (i=2; i<=n; i++)
		if (dist[i]== BIG )
			g<<0<<' ';
		else
			g<<dist[i]<<' ';
		
	g.close();
	return 0;
}