#include <stdio.h>
#include <string.h>
#include <vector>
#define N 1<<16
#define NMAX 1<<20
#define Q 1<<6
#define inf 1000000000
using namespace std;
int n,m,cost[N],r,coada[NMAX];
vector <pair <int,int> > vecini[N];
char stiva[N],line[Q];
inline int cif(char x)
{
	return x>='0' && x<='9';
}
void read()
{
	scanf("%d%d\n",&n,&m);
	int i,j,nr[4],poz;
	for (i=1; i<=m; i++)
	{
		fgets(line+1,Q,stdin);
		poz=1;
		for (j=1; j<=3; j++)
		{
			nr[j]=0;
			while (line[poz]==' ')
				poz++;
			while (cif(line[poz]))
				nr[j]=nr[j]*10+line[poz]-'0',poz++;
		}
		vecini[nr[1]].push_back(make_pair(nr[2],nr[3]));
	}
}
void solve()
{
	coada[++r]=1;
	stiva[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++)
		{
			stiva[coada[i]]=0;
			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;
					if (!stiva[vecini[coada[i]][j].first])
					{
						coada[++r]=vecini[coada[i]][j].first;
						stiva[vecini[coada[i]][j].first]=1;
						ok=1;
					}
				}
		}
		ant=act;
	}
}
void time_for_the_real_show()
{
	int i;
	for (i=2; i<=n; i++)
		printf("%d ",cost[i]!=inf ? cost[i] : 0);
	printf("\n");
}
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	read();
	solve();
	time_for_the_real_show();
	return 0;
}