#include<fstream>
#define NM 50001
#define inf 1<<25
#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(po&&D[H[po]]<D[H[po>>1]])
	{
		swap(H[po],H[po>>1]);
		swap(P[H[po]],P[H[po>>1]]);
		po>>=1;
	}
}
void coboara(int po){
    int y=0;
    while(po!=y){
        y=po;
        if((y<<1)<=L&&D[H[y<<1]]<D[H[po]])
            po=y<<1;
        if((y<<1)+1<=L&&D[H[(y<<1)+1]]<D[H[po]])
            po=(y<<1)+1;
        swap(H[po],H[y]);
        swap(P[H[po]],P[H[po]]);
    }
}
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];
		H[1]=H[L];
		P[H[1]]=1;
		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;
					urca(L);
				}
			}
		}
	}
	for(i=2;i<=n;++i)
		if(D[i]==inf)
			g<<"0 ";
		else
			g<<D[i]<<" ";
	return 0;
}