#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;

struct heap
{
	int valoare;
	int indice;
};

heap H[NMAX];

//Schimba:
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:
void push_up(int l)
{
	while(H[l].valoare<H[l/2].valoare)
	{
		swap(l,l/2);
		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);
		else if(H[l*2+1].valoare>H[l*2].valoare && H[l].valoare>H[l*2].valoare)
			swap(l,l*2);
	}
	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)
		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(poz[ind]);
}
//Modifica:
void change(int val, int ind)
{
	H[ind].valoare=val;
	relax(ind);
}
//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(y);
			C[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();
}
//Init:
void init()
{
	for(int i=2;i<=N;i++)
		d[i]=INF;
	add(0,1);
}
//Dijkstra:
void dij()
{
	int x;
	unsigned int i;
	while(Lung)
	{
		x=H[1].indice;
		sterge(1);
		for(i=0;i<G[x].size();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]);
				}
			}
		}
	}
}

//Debug:
void Debug()
{
	cout<<"Lista de vecini:\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";
		}
	cout<<"Lista de costuri:\n";
	for(int j=1;j<=N;j++)
		{
			cout<<j<<": ";
			for(unsigned int i=0;i<C[j].size();i++)
				cout<<C[j][i]<<" ";
			cout<<"\n";
		}
}

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