#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#define NMAX 55001
#define MAX 250001
#define POS 500001
#define INF 1000000000
#define CARACTER 101
using namespace std;
void initializare();
void citire();
void sortare();
void rezolvare();
void scrie();
int N,M;
vector<int> G[NMAX],H[NMAX];
int COADA[POS],NR=0;
int VAL[POS];
bool bou=0;

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

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

void citire()
{
	int a,val[5],d;
	char ch[CARACTER];
	scanf("%d %d\n",&N,&M);
	for(int i=1;i<=M;i++)
	{
		fgets(ch,CARACTER,stdin);
		d=0;a=0;
		for(int k=0; ch[k]!='\n' && ch[k]!=EOF;k++)
			if(ch[k]==' ')
				val[++d]=a,a=0;
			else
				a=10*a+ch[k]-'0';
		val[++d]=a;
		G[val[1]].push_back(val[2]);
		H[val[1]].push_back(val[3]);
	}
		
}

void sortare()
{
	vector<int>::iterator it;
	int e[250001],j;
	for(int i=1;i<=N;i++)
	{
		j=0;
		for(it=G[i].begin();it!=G[i].end();it++)
			e[++j]=*it;
		G[i].erase(G[i].begin(),G[i].end());
		sort(e,e+j+1);
		for(int l=1;l<=j;l++)
			G[i].push_back(e[l]);
	}
			
}

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

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