#include <fstream>
#include <vector>
using namespace std;
const int NMAX=50003;
const int oo=60000003;
struct nod {int v; short c;};
vector <nod> A[NMAX];
vector <int> d;
int nv[NMAX],n,nh,H[NMAX];

void citire()
{
	ifstream fin("dijkstra.in");
	int m,i;
	fin>>n>>m;
	memset (nv,0,sizeof(nv));
	for (i=1;i<=m;++i)
	{ int x; nod z;
	  fin>>x>>z.v>>z.c;  ++nv[x];
	  A[x].push_back(z);	  
	}
	fin.close();
}

void sift(int k)
{ int fiu;
	do
	{
		fiu=k<<1; 
		if (fiu<=nh)
			{
				if (fiu+1<nh)
					if (d[H[fiu+1]]<d[H[fiu]]) fiu++;
				if (d[H[k]]>d[H[fiu]]) {
									int aux=H[fiu]; H[fiu]=H[k]; H[k]=aux;
									k=fiu;
								 }
						else fiu=0;
			}
		   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]; k>>=1;}
	H[k]=val;
}


void calc()
{
	bool viz[NMAX]; d.resize(n+4,oo);
	memset(viz,0,sizeof(viz));
	d[1]=0; nh=1; H[1]=1;			
	while (nh)
	{ int m,i,x;
		m=H[1]; H[1]=H[nh--]; sift(1); 
		viz[m]=true;
		for (i=0;i<nv[m];++i)
		{ x=A[m][i].v;
		 if (!viz[x])
			if (d[x]>d[m]+A[m][i].c)
		       { d[x]=d[m]+A[m][i].c; 
				 H[++nh]=x; percolate(nh);
			   }	
		}		
	}	
}

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

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