#include <fstream>
#include <vector>
using namespace std;
const int oo=0x3f3f3f3f;
const int NMAX=50002;
vector < pair<int,short> > L[NMAX];
int n,d[NMAX],ph[NMAX],H[NMAX],nh;

void citire()
{
	ifstream fin("dijkstra.in");
	int m,i;
	fin>>n>>m;
	for (i=0;i<m;++i)
	{ int x,y; short ct;
		fin>>x>>y>>ct;
		L[x].push_back( make_pair(y,ct) );		
	}
	fin.close();
}

void sift(int k)
{ int fiu;
	do
	{
		fiu=0;
		if ((k<<1)<=nh)
		 {
			fiu=k<<1;
			if (fiu<nh && d[H[fiu+1]]<d[H[fiu]])  ++fiu;
			if (d[H[fiu]]<d[H[k]])
				{
				  int aux=H[fiu]; H[fiu]=H[k]; H[k]=aux;
				  ph[H[fiu]]=fiu; ph[H[k]]=k;
				  k=fiu;
				}
				else fiu=0;
		 }		
	}
	while (fiu);
}

void percolate(int k)
{  int val=H[k];
	while (k>1 && d[val]<d[H[k>>1]])
	{
		H[k]=H[k>>1]; ph[H[k]]=k;
		k>>=1;
	}
	H[k]=val; ph[val]=k;
}

void dijkstra()
{ int i;
	for (i=1;i<=n;++i) {H[i]=i; d[i]=oo; ph[i]=i;}
	H[1]=1; d[1]=0;
	for (nh=n;nh>1;)
	{
		int x=H[1]; H[1]=H[nh--]; ph[H[1]]=1; sift(1);
		for (i=0;i<L[x].size();++i)
		 if (d[L[x][i].first]>d[x]+L[x][i].second)
			{
			  d[L[x][i].first]=d[x]+L[x][i].second;
			  percolate(ph[L[x][i].first]);
			}
	}
}

void afisare()
{
	ofstream fout("dijkstra.out");
	for (int i=2;i<=n;++i)
	    if (d[i]==oo) fout<<"0 ";
			else fout<<d[i]<<" ";
	fout.close();
}

int main()
{
	citire();
	dijkstra();
	afisare();
	return 0;
}