#include<fstream>
#define NM 50001
#define inf 1<<30
#include<vector>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct el{ int d,c; };
el no;
int P[NM],H[NM],nd,L,n,m,i,x,D[NM];
vector<el>A[NM];
int mi(int a,int b)
{
	if(D[H[a]]<D[H[b]])
		return a;
	return b;
}
void urca(int po)
{
	while(D[H[po]]<D[H[po>>1]]&&po>1)
	{
		swap(H[po],H[po>>1]);
		swap(P[H[po]],P[H[po>>1]]);
		po>>=1;
	}
}
void coboara(int po)
{
	int nod;
	while((po<<1)<=L&&D[H[po]]>D[H[po<<1]])
	{
		if((po<<1)!=L)
		{
			nod=mi(po<<1,(po<<1)+1);
			swap(H[po],H[nod]);
			swap(P[H[nod]],P[H[po]]);
			po<<=1;
		}
		else
		{
			swap(H[po],H[po<<1]);
			swap(P[H[po]],P[H[po<<1]]);
			break;
		}
	}
}
int main ()
{
	f>>n>>m;
	for(i=1;i<=m;++i)
	{
		f>>x>>no.d>>no.c;
		A[x].push_back(no);
	}
	H[1]=1; P[1]=1;
	for(i=2;i<=n;++i)
		D[i]=inf;
	L=1;
	while(L)
	{
		int nd=H[1];
		P[H[1]]=0;
		H[1]=H[L];
		L--;
		coboara(1);
		for(i=0;i<A[nd].size();++i)
		{
			int des=A[nd][i].d;
			int cos=A[nd][i].c;
			if(D[nd]+cos<=D[des])
			{
				D[des]=D[nd]+cos;
				if(P[des])
				urca(P[des]);
				else
				{
					++L;
					P[des]=L;
					H[L]=des;
				}
			}
		}
	}
	for(i=2;i<=n;++i)
		if(D[i]==inf)
			g<<"0 ";
		else
			g<<D[i]<<" ";
	return 0;
}