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

#define NMAX 50001
#define INF 0x3f3f3f3f

using namespace std;

//Variabile Globale:
vector<int> V[NMAX],G[NMAX];

int N;
int d[NMAX];
int poz[NMAX];

struct heap
{
	int valoare;
	int indice;
};

heap H[NMAX];
int Lung;

//Functia de interschimbare supraincarata int si heap:
inline void schimba(int &a, int &b)
{
	int aux;
	aux=a;
	a=b;
	b=aux;
}

inline void schimba(heap &a, heap &b)
{
	heap aux;
	aux=a;
	a=b;
	b=aux;
}

//Functia de Urcare:
inline void push_up(int l)
{
	while(H[l].valoare<H[l/2].valoare)
	{
		schimba(H[l],H[l/2]);
		schimba(poz[H[l].indice],poz[H[l/2].indice]);
	}
}

//Functia de Coborare:
inline void push_down(int l)
{
	/*
	Verificam daca exista un fiu, doi, sau nici unul si facem schimbarea 
	cu minumul dintre ei.
	*/
	if((l*2+1<=Lung) && (H[l*2+1].valoare<H[l*2].valoare) && (H[l].valoare>H[l*2+1].valoare))
	{
		schimba(H[l*2+1],H[l]);
		schimba(poz[H[l*2+1].indice],poz[H[l].indice]);
		push_down(l*2+1);
	}
	else if((l*2+1<=Lung) && (H[l*2+1].valoare>H[l*2].valoare) && (H[l].valoare>H[l*2].valoare))
	{
		schimba(H[l*2],H[l]);
		schimba(poz[H[l*2].indice],poz[H[l].indice]);
		push_down(l*2);
	}
	else if((l*2==Lung) && (H[l*2].valoare<H[l].valoare))
	{
		schimba(H[l*2],H[l]);
		schimba(poz[H[l*2].indice],poz[H[l].indice]);
	}

}
//Functia de Relaxare dupa extragere:
void relax(int l)
{
	if(H[l].valoare<H[l/2].valoare)
		push_up(l);
	else push_down(l);
}

//Functia de Extragere a minimului:
void extrage_min()
{

	schimba(poz[H[1].indice],poz[H[Lung].indice]);
	schimba(H[1],H[Lung]);
	H[Lung].valoare=0;
	H[Lung].indice=0;
	poz[H[Lung].indice]=0;
	Lung--;
	relax(1);
}

//Functia de Modificare in heap:
inline void modifica(int l,int val)
{
	H[l].valoare=val;
	push_up(l);
}

//Dijkstra+Heap algo:
void Dijkstra()
{
	int x;
	unsigned int i;
	while(Lung!=0)
	{
		x=H[1].indice;
		extrage_min();
		for(i=0;i<V[x].size();i++)
		{
			if(d[x]+G[x][i]<d[V[x][i]])
			{
				d[V[x][i]]=d[x]+G[x][i];
				modifica(poz[V[x][i]],d[x]+G[x][i]);
			}
		}
	}
}

//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;
			V[x].push_back(y);
			G[x].push_back(c);
		}
	fin.close();
}

//Functia de Afisare a vectorului d[]:
void afisare()
{
	ofstream fout("dijkstra.out");
	for(register int i=2;i<=N;i++)
		if(d[i]!=INF) fout<<d[i]<<" ";
		else fout<<"0 ";
	fout<<"\n";
	fout.close();
}

//Initializari:
void init()
{
	for(int i=2;i<=N;i++)
	{
		d[i]=INF;
		H[i].valoare=INF;
		poz[i]=i;
		H[i].indice=i;
	}
	H[1].indice=1;
	poz[1]=1;
	Lung=N;
	H[1].valoare=0;
}

//Debug:
void Debug()
{
	cout<<"Lista de vecini:\n";
	for(int j=1;j<=N;j++)
		{
			cout<<j<<": ";
			for(unsigned int i=0;i<V[j].size();i++)
				cout<<V[j][i]<<" ";
			cout<<"\n";
		}
	cout<<"\nLista de costuri:\n";
	for(int j=1;j<=N;j++)
		{
			cout<<j<<": ";
			for(unsigned int i=0;i<G[j].size();i++)
				cout<<G[j][i]<<" ";
			cout<<"\n";
		}
}

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