#include<fstream>
#include<iostream>
#include<vector>
using namespace std;
int n,m,x0,N;
struct Nod{int x,c;};
vector <Nod> G[50010];
vector <Nod>::iterator it;
int M[50010],pre[50010],d[50010],H[50010];

void Citire()
{
	int i,x,y,c;
	Nod aux;
	ifstream fin("dijkstra.in");
	fin>>n>>m;
	for(i=1;i<=m;i++)
	{
		fin>>x>>y>>c;
		aux.x=y;
		aux.c=c;
		G[x].push_back(aux);
	}
	fin.close();
}

void Initializari()
{
	int i;
	for(i=2;i<=n;i++)
		d[i]=2000000000;
	d[1]=0;
	pre[1]=0;
}

void InsertHeap(int x)
{
	int fiu,tata;
	fiu=++N;
	tata=fiu/2;
	while(tata && d[H[tata]]>d[x])
	{
		H[fiu]=H[tata];
		fiu=tata;
		tata=fiu/2;
	}
	H[fiu]=x;
}

void CombHeap(int i)
{
	int x,tata,fiu;
	tata=i; 
	fiu=2*i;
	x=H[tata];
	while(fiu<=N)
	{
		if(fiu<N) 
			if(d[H[fiu]]>d[H[fiu+1]])
				fiu++;
		if(d[x]>d[H[fiu]])
		{
			H[tata]=H[fiu];
			tata=fiu; 
			fiu=fiu*2;
		}
		else
			fiu=N+1; 
	}
	H[tata]=x;
}

int ExtractMin()
{
	int sol=H[1];
	H[1]=H[N--];
	CombHeap(1);
	return sol;
}

int Cauta(int nod)
{
	int i;
	for(i=1;i<=N;i++)
		if(H[i]==nod)
			return i;
	return 1;
}

void Actualizeaza(int nod,int x)
{
	int fiu=Cauta(nod),tata;
	tata=fiu/2;
	while(tata && x<d[H[tata]])
	{
		H[fiu]=H[tata];
		fiu=tata;
		tata=fiu/2;
	}
	H[fiu]=nod;
}

void Dijkstra()
{
	int i,vfmin,dmin;
	Nod aux;
	for(i=1;i<=n;i++)
		InsertHeap(i);
	for(i=1;i<n;i++)
	{
		vfmin=ExtractMin();
		dmin=d[vfmin]; 
		M[vfmin]=1;
		for(it=G[vfmin].begin();it!=G[vfmin].end();it++)
		{
			aux=*it;
			if(d[aux.x]>d[vfmin]+aux.c)
			{
				d[aux.x]=d[vfmin]+aux.c;
				pre[aux.x]=vfmin;
				Actualizeaza(aux.x,d[aux.x]);
			}
		}
	}
}

void Afisare()
{
	int i;
	ofstream fout("dijkstra.out");
	for(i=2;i<=n;i++)
		fout<<d[i]<<' ';
	fout<<"\n";
	fout.close();
}

int main()
{
	Citire();
	
	Initializari();
	
	Dijkstra();
	
	Afisare();
	
	return 0;
}