#include <stdio.h>
#include <vector>
#define NMAX 50001
#define LMAX 1<<17
#define INF 1000000000
#define mp make_pair
#define pb push_back
#define f first
#define s second
using namespace std;
int n,m,cost[NMAX],init[NMAX];
vector < pair <int,int> > v[NMAX];
struct arbint
{
	int a,b;
};
arbint arb[LMAX];
void read()
{
	scanf("%d%d",&n,&m);
	int x,y,z;
	while (m)
	{
		scanf("%d%d%d",&x,&y,&z);
		v[x].pb(mp(y,z));
		m--;
	}
}
void initialise()
{
	int i;
	for (i=2; i<=n; i++)
		cost[i]=INF;
}
void cstr(int nod,int st,int dr)
{
	arb[nod].a=INF;
	if (st==dr)
	{
		init[st]=nod;
		return ;
	}
	int mij=(st+dr)/2;
	cstr(2*nod,st,mij);
	cstr(2*nod+1,mij+1,dr);
}
void update(int poz,int val)
{
	int k=init[poz];
	arb[k].a=val; arb[k].b=poz;
	for (k/=2; k>0; k/=2)
		if (arb[2*k].a<arb[2*k+1].a)
		{
			arb[k].a=arb[2*k].a;
			arb[k].b=arb[2*k].b;
		}
		else
		{
			arb[k].a=arb[2*k+1].a;
			arb[k].b=arb[2*k+1].b;
		}
}
void solve()
{
	update(1,0);
	int i,poz,val=0,x,y;
	while (val!=INF)
	{
		poz=arb[1].b; val=arb[1].a;
		update(poz,INF);
		for (i=0; i<v[poz].size(); i++)
		{
			x=v[poz][i].f; y=v[poz][i].s;
			if (cost[poz]+y<cost[x])
			{
				cost[x]=cost[poz]+y;
				update(x,cost[x]);
			}
		}
	}
}
void show()
{
	int i;
	for (i=2; i<=n; i++)
		printf("%d ",cost[i]==INF ? 0 : cost[i]);
	printf("\n");
}
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	read();
	initialise();
	cstr(1,1,n);
	solve();
	show();
	return 0;
}