#include <fstream>
#include <vector>
#include <utility>
#define Inf 2000000000
#define N 50010
using namespace std;

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

vector <pair <int,short> > a[N];
int h[N],p[N],d[N],n,m,i,j,k,nh,y,z,x;
vector <pair <int,short> >::iterator t;
pair <int,short> u;

int main () {
	in>>n>>m;
	nh=n;
	while (m--) {
		in>>i>>u.first>>u.second;
		a[i].push_back (u);
	}
	for (i=1; i<=n; i++) {
		d[i]=Inf;
		h[i]=p[i]=i;
	}
	d[1]=0;
	while (nh) {
		k=h[1];
		p[k]=nh; p[h[nh]]=1;
		h[1]=h[nh--];
		x=1;
		while (1) {
			z=x<<1;
			if (z<=nh) {
				if (d[h[x]]>d[h[z]]) y=z;
				if (z<nh)
					if (d[h[y]]>d[h[z+1]]) y=z+1;
			}
			else break;
			if (x==y) break;
			p[h[x]]=y; p[h[y]]=x;
			h[x]^=h[y]; h[y]^=h[x]; h[x]^=h[y];
			x=y;
		}
		for (t=a[k].begin (); t!=a[k].end (); t++) {
			j=(*t).first;
			if (p[j]<=nh) {
				if (d[k]+(*t).second<d[j]) {
					d[j]=d[k]+(*t).second;
					j=p[j];
					while (j>1&&d[h[y=(j>>1)]]>d[h[j]]) {
						p[h[j]]=y; p[h[y]]=j;
						h[j]^=h[y]; h[y]^=h[j]; h[j]^=h[y];
						j=y;
					}
				}
			}
		}
	}
	for (i=2; i<=n; i++) {
		if (d[i]==Inf) out<<"0 ";
		else out<<d[i]<<" ";
	}
	out<<"\n";
	return 0;
}