//14:37

#include <stdio.h>
#include <queue>
#define infile "dijkstra.in"
#define outfile "dijkstra.out"
#define NMAX 50005
#define INF 50000005
using namespace std;

typedef struct snod{int x,c;snod *nxt;}*L;
L G[NMAX];
int N,M,cost[NMAX];
short int incoada[NMAX];
queue <int> coada;

void citire(),rezolvare(),afisare();

int main()
{
	freopen(infile,"r",stdin);
	freopen(outfile,"w",stdout);
	
	citire();
	rezolvare();
	afisare();
	
}

void afisare()
{
	for(int i=2;i<=N;i++)
		printf("%d ",cost[i]!=INF?cost[i]:0);
	printf("\n");
}


//bellman-ford cu coada
inline void push(int nod)
{
	if(!incoada[nod])
	{
		incoada[nod]=1;
		coada.push(nod);
	}
}

inline int first()
{
	int aux=coada.front();
	coada.pop();
	incoada[aux]=0;
	return aux;
}

void init()
{
	for(int i=2;i<=N;i++)
		cost[i]=INF;
}

void rezolvare()
{
	init();
	push(1);
	while(!coada.empty())
	{
		int nod=first();
		for(L p=G[nod];p;p=p->nxt)
			
			//actualizam costul
			if(cost[nod]+(p->c)<cost[p->x])
			{
				cost[p->x]=cost[nod]+(p->c);
				push(p->x);
			}
	}
}

//citim din fisier
inline void add(int s, int d, int c)
{
	L aux=new snod;
	aux->x=d;
	aux->c=c;
	aux->nxt=G[s];
	G[s]=aux;
}

void citire()
{
	int i,s,d,c;
	scanf("%d %d",&N,&M);
	for(i=1;i<=M;i++)
	{
		scanf("%d %d %d",&s,&d,&c);
		add(s,d,c);
	}
}