#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;
vector <pair <int,short> >::iterator t;
pair <int,short> u;
short s;

void up (int x) {
	while (x>1&&d[h[y=(x>>1)]]>d[h[x]]) {
		p[h[x]]=y; p[h[y]]=x;
		z=h[x]; h[x]=h[y]; h[y]=z;
		x=y;
	}
}

void down (int x) {
	while (1) {
		z=x<<1;
		if ((z)<=nh&&d[h[x]]>d[h[z]]) y=z;
		if ((z)<nh&&d[h[y]]>d[h[z+1]]) y=z+1;
		if (x==y) break;
		p[h[x]]=y; p[h[y]]=x;
		z=h[x]; h[x]=h[y]; h[y]=z;
		x=y;
	}
}

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];
		nh--;
		down (1);
		for (t=a[k].begin (); t!=a[k].end (); t++) {
			j=(*t).first;
			if (p[j]<=nh) {
				s=(*t).second;
				if (d[k]+s<d[j]) {
					d[j]=d[k]+s;
					up (p[j]);
				}
			}
		}
	}
	for (i=2; i<=n; i++) {
		if (d[i]==Inf) out<<"0 ";
		else out<<d[i]<<" ";
	}
	out<<"\n";
	return 0;
}