#include <fstream>
#include <iostream>
#include <vector>

#define NMAX 50001
#define INF 0x3f3f3f3f

using namespace std;
//Variabile Globale:
vector<int> G[NMAX],C[NMAX];
int N;
int d[NMAX];
int poz[NMAX];
int Lung;
int viz[NMAX];

struct heap
{
	int valoare;
	int indice;
};

heap H[NMAX];

//Schimba:
inline void swap(int a, int b)
{
	int aux;
	aux=poz[H[a].indice];
	poz[H[a].indice]=poz[H[b].indice];
	poz[H[b].indice]=aux;
	
	heap auxi;
	auxi=H[a];
	H[a]=H[b];
	H[b]=auxi;
}

//Urca:
inline void push_up(int l)
{
	while(H[l].valoare<H[l/2].valoare && l!=1)
	{
		swap(l,l/2);
		l=l/2;
	}
}

//Coboara:
void push_down(int l)
{
	if(l*2+1<=Lung)
	{
		if(H[l*2+1].valoare<=H[l*2].valoare && H[l].valoare>=H[l*2+1].valoare)
			{
				swap(l,l*2+1);
				push_down(l*2+1);
			}
		else if(H[l*2+1].valoare>=H[l*2].valoare && H[l].valoare>=H[l*2].valoare)
			{
				swap(l,l*2);
				push_down(l*2);
			}
	}
	else if(l*2==Lung)
	{
		if(H[l].valoare>H[l*2].valoare)
			{
				swap(l,l*2);
				push_down(l*2);
			}
		
	}
}

//Relax:
void relax(int l)
{
	if(H[l].valoare<H[l/2].valoare && l!=1)
		push_up(l);
	else push_down(l);
}

//Adauga:
void add(int val, int ind)
{
	H[++Lung].valoare=val;
	H[Lung].indice=ind;
	poz[ind]=Lung;
	push_up(Lung);
}
//Modifica:
inline void change(int val, int l)
{
	H[l].valoare=val;
	push_up(l);
}
//Sterge:
void sterge(int l)
{
	if(l!=Lung)
	{
		swap(l,Lung);
		poz[H[Lung].indice]=0;
//		H[Lung].indice=0;
//		H[Lung].valoare=0;
		Lung--;
		push_down(l);
	}
	else
	{
		poz[H[l].indice]=0;
//		H[l].indice=0;
//		H[l].valoare=0;
		Lung--;
	}
}

//Functia de Citire:
void citire()
{
	ifstream fin("dijkstra.in");
	int M,x,y,c;
	fin>>N>>M;
	for(int i=1;i<=M;i++)
		{
			fin>>x>>y>>c;
			G[x].push_back(y);
			C[x].push_back(c);
		}
	fin.close();
}
//Functia de Afisare a vectorului d[]:
void afisare()
{
	ofstream fout("dijkstra.out");
	for(int i=2;i<=N;i++)
		if(d[i]!=INF) fout<<d[i]<<" ";
		else fout<<"0 ";
	fout<<"\n";
	fout.close();
}
//Init:
void init()
{
	add(0,1);
	for(int i=2;i<=N;i++)
	{
		d[i]=INF;
	}
	

	
}
//Dijkstra:
void dij()
{
	
	int x;
	unsigned int i;
	while(Lung)
	{
		
		x=H[1].indice;
		sterge(1);
		viz[x]++;
		
		for(i=0;i<G[x].size();i++)
		{
			if(!viz[G[x][i]])
				if(d[x]+C[x][i]<d[G[x][i]])
				{
					d[G[x][i]]=d[x]+C[x][i];
					
					if(poz[G[x][i]])
						change(d[G[x][i]],poz[G[x][i]]);
					else 
						add(d[G[x][i]],G[x][i]);
				
				}
		}
	}
}

//Main:
int main(int argc, char *argv[])
{
	citire();
	
	init();
	
	dij();
	
	afisare();
}