#include <stdio.h>
#include <string.h>
#include <vector>
#define N 1<<16
#define NMAX 1<<20
#define inf 1000000000
using namespace std;
int n,m,cost[N],coada[NMAX],r;
vector <pair <int,int> > vecini[N];
char viz[N];
void read()
{
	scanf("%d%d",&n,&m);
	int i,x,y,z;
	for (i=1; i<=m; i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		vecini[x].push_back(make_pair(y,z));
	}
}
void solve()
{
	coada[++r]=1;
	viz[1]=1;
	int i,j,ok=1,ant=0,act;
	for (i=1; i<=n; i++)
		cost[i]=inf;
	cost[1]=0;
	while (ok)
	{
		act=r;
		ok=0;
		for (i=ant+1; i<=act; i++)
			for (j=0; j<vecini[coada[i]].size(); j++)
				if (cost[coada[i]]+vecini[coada[i]][j].second<cost[vecini[coada[i]][j].first])
				{
					cost[vecini[coada[i]][j].first]=cost[coada[i]]+vecini[coada[i]][j].second;
					coada[++r]=vecini[coada[i]][j].first;
					ok=1;
				}
		ant=act;
	}
}
void time_for_the_real_show()
{
	int i;
	for (i=2; i<=n; i++)
		printf("%d ",cost[i]);
	printf("\n");
}
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	read();
	solve();
	time_for_the_real_show();
	return 0;
}