//100%working
#include <fstream>
#include <iostream>
#include <vector>


#define NMAX 50001
#define INF 0x3f3f3f3f

using namespace std;
//Variabile Globale:
vector<pair<int,int> > G[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)
{
	eticheta:
	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);
				l=l*2+1;
				goto eticheta;
			}
		else if(H[l*2+1].valoare>=H[l*2].valoare && H[l].valoare>=H[l*2].valoare)
			{
				swap(l,l*2);
				l=l*2;
				goto eticheta;
			}
	}
	else if(l*2==Lung)
	{
		if(H[l].valoare>H[l*2].valoare)
			{
				swap(l,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--;
		relax(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(make_pair(y,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);
	memset(d,INF,sizeof(d));
	d[1]=0;
	
}
//Dijkstra:
void dij()
{
	
	int x;
	while(Lung)
	{
		
		x=H[1].indice;
		sterge(1);
		viz[x]++;
		
		for(vector<pair <int,int> >::iterator i=G[x].begin();i!=G[x].end();i++)
		{
			if(!viz[i->first])
				if(d[x]+i->second<d[i->first])
				{
					d[i->first]=d[x]+i->second;
					
					if(poz[i->first])
						change(d[i->first],poz[i->first]);
					else 
						add(d[i->first],i->first);
				
				}
		}
	}
}

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