#include<stdio.h>
#include<fstream>
#include<vector>
#define Nmax 50002
#define inf 0x3f3f3f
using namespace std;

ifstream c("dijkstra.in");
ofstream g("dijkstra.out");

typedef struct nod {int x,cost;}NOD;
vector <NOD> a[Nmax];
int n,m,d[Nmax],position[Nmax],heap[Nmax],s=1;          //p reprezinta vectorul de pozitie al nodului i in heap
int heap_size;                                                 // numarul de elemente din heap

inline void read()
{
	int i,y;
	NOD z;
	c>>n>>m;
	for(i=1;i<=m;i++)
	{
		c>>y>>z.x>>z.cost;
		a[y].push_back(z);
	}
}

inline void swap_procedure(int a,int b)
{
	int aux;
	aux=heap[a];       // Interschimbam nodurile din heap
	heap[a]=heap[b];
	heap[b]=aux;                             
	aux=position[heap[a]];                // Interschimbam si pozitiile nodurilor care s-au interschimbat din heap 
	position[heap[a]]=position[heap[b]];
	position[heap[b]]=aux;
	
}

inline void min_heapify_down(int nr,int i)
{
	int l,r,max=i;       //d[heap[l]],d[heap[r]] ,adica distantele varfurilor care sunt fii nodului parinte trebuie sa fie mai mari decat ale parintelui 
	l=i<<1;
	r=l+1;
	if(l<=nr&&d[heap[l]]<d[heap[i]])
		max=l;
	if(r<=nr&&d[heap[r]]<d[heap[max]])
		max=r;
	if(max!=i)
	{
		swap_procedure(i,max);
		min_heapify_down(nr,max);
	}
}

inline void min_heapify_up(int nr,int i)
{
	int p,min=i;
	p=i>>1;
	if(p>=1&&d[heap[p]]>d[heap[i]])
		min=p;
	if(min!=i)
	{
		swap_procedure(i,min);
		min_heapify_up(nr,min);
	}
}

inline void delete_from_heap(int &nr,int i)
{
	swap_procedure(i,nr); 
	position[heap[nr]]=-1;
	nr--;
	if((i<<1<=nr&&d[heap[i<<1]]<d[heap[i]])||(i<<1+1<=nr&&d[heap[i<<1+1]]<d[heap[i]]))
		min_heapify_down(nr,i);
	else
		if(i>>1>=1&&d[heap[i>>1]]>d[heap[i]])
			min_heapify_up(nr,i);
}
	

inline void dijkstra_with_heap()
{
	int i,nod_curent;         // nod_curent reprezinta nodul cel mai apropiat de s-nodul pentru care aflam distantele minime
	d[s]=0;                                         // adica nodul din varful heap-ului
	heap[1]=s;
	heap_size=1;
	position[s]=1;                              // pozitia lui s in heap
	for(i=2;i<=n;i++)                 // i incepe de la 2 pentru a nu modifica d[s],unde s=1,adica distanta de la 1 la 1 este 0
	{
		d[i]=inf;
		position[i]=-1;
	}
	while(heap_size>=1)
	{
		nod_curent=heap[1];
		delete_from_heap(heap_size,1);
		for(i=0;i<a[nod_curent].size();i++)
			if(d[nod_curent]+a[nod_curent][i].cost<d[a[nod_curent][i].x])
			{
				d[a[nod_curent][i].x]=d[nod_curent]+a[nod_curent][i].cost;
				if(position[a[nod_curent][i].x]==-1)                  // adaugam nodul in heap
				{
					heap_size++;
					heap[heap_size]=a[nod_curent][i].x;
					position[a[nod_curent][i].x]=heap_size;              // punem in position pozitia din heap a nodului gasit 
				}
				min_heapify_up(heap_size,heap_size);
			}
	}
}

inline void write()
{
	int i;
	for(i=2;i<=n;i++)
		if(d[i]!=inf)
			g<<d[i]<<" ";
		else
			g<<"0 ";
}

int main()
{
	read();
	dijkstra_with_heap();
	write();
	return 0;
}