#include <cstdio>
#include <vector>
#define NMAX 50001
#define INF 1000000000
using namespace std;
void initializare();
void citire();
void rezolvare();
void scrie();
int minim(int a,int b);
int N,M;
vector<int> G[NMAX],H[NMAX];
int COADA[NMAX],NR=0;
int VAL[NMAX];
bool bou=0;

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	initializare();
	citire();
	rezolvare();
	scrie();
	
	return 0;
}

void initializare()
{
	for(int i=1;i<=NMAX;i++)
		VAL[i]=INF;
}

void citire()
{
	int x,y,v;
	scanf("%d %d",&N,&M);
	for(int i=1;i<=M;i++)
	{
		scanf("%d %d %d",&x,&y,&v);
		G[x].push_back(y);
		H[x].push_back(v);
	}
		
}

void rezolvare()
{
	vector<int>::iterator it,ih;
	
	for( it=G[1].begin(), ih=H[1].begin(); it!=G[1].end() || ih!=H[1].end() ;it++,ih++)
	{
		COADA[++NR]=*it;
		VAL[COADA[NR]]=*ih;
	}
	
	for(int i=1;i<=NR;i++)
		for( it=G[COADA[i]].begin(), ih=H[COADA[i]].begin(); it!=G[COADA[i]].end() || ih!=H[COADA[i]].end() ;it++,ih++)
			if(*ih+VAL[COADA[i]]<VAL[*it])
			{
				COADA[++NR]=*it;
				VAL[COADA[NR]]=minim(VAL[COADA[NR]],*ih+VAL[COADA[i]]);
			}
}

void scrie()
{
	for(int i=2;i<=N;i++)
		printf("%d ",VAL[i]);
}

int minim(int a,int b)
{

	if(a>b)
		return b;

	return a;
}