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

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


using namespace std;


struct grf{
	int ori,tar,dst;
}constr;
	
vector <grf> v[50001];

vector<pair <int,grf> >  frontier(5);
int dist[50001];

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

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

pair <int,grf> getHeap() {
	pair <int,grf> 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,grf> x) {
	//frontier[++frontier[0].ff]=x;
	frontier[0].ff++;
	frontier.insert(frontier.begin()+1,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 i,j,n,m;
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	f>>n>>m;
	for (i=1; i<=m; i++) {
		f>>constr.ori;
		f>>constr.tar>>constr.dst;
		v[constr.ori].push_back(constr);
	}
	pair <int,grf> sw;
	pair <int,grf> entr;
	
	for (i=0; i<v[1].size(); i++) {
		sw.ff=v[1][i].dst;
		sw.ss=v[1][i];
		insertHeap(sw);
	}
	while (frontier[0].ff) {
		sw=getHeap();
		if (!dist[sw.ss.tar]) {
			dist[sw.ss.tar]=dist[sw.ss.ori]+sw.ss.dst;
			for (i=0; i<v[sw.ss.tar].size(); i++) {
				entr.ss=v[sw.ss.tar][i];
				entr.ff=sw.ff+entr.ss.dst;
				insertHeap(entr);
			}
		}
	}
	
	for (i=2; i<=n; i++)
		g<<dist[i]<<' ';
	g<<'\n';
	g.close();
	return 0;
}