#include<cstdio>
#include<fstream>
#include<vector>
#include<utility>
using namespace std;

int n,m,x,y,c,i,L,oo=1<<30,d[50010],H[50010],P[50010];
vector<pair<int,int> > V[50010];
void read(),solve(),heap_up(int),heap_down(int);
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int main()
{
	read();
	solve();
	
	return 0;
}

void read()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	//scanf("%d%d",&n,&m);
	f>>n>>m;
	for(;m;m--)
	{
		//scanf("%d%d%d",&x,&y,&c);
		f>>x>>y>>c;
		V[x].push_back(make_pair(y,c));
	}
}

void solve()
{
	vector<pair<int,int> >::iterator it;
	for(i=1;i<=n;i++){d[i]=oo;H[i]=i;P[i]=i;}//initializare
	d[1]=0;
	L=n;
	for(;L;)
	{
		x=H[1];
		for(it=V[x].begin();it!=V[x].end();it++)
		{
			y=it->first;c=it->second;
			if(d[y]>d[x]+c)
			{
				d[y]=d[x]+c;
				heap_up(P[y]);
			}
		}
		H[1]=H[L];
		P[H[L]]=1;
		L--;
		heap_down(1);
	}
	for(i=2;i<=n;i++)d[i]==oo?g<<"0 ":g<<d[i]<<' ';
}

void heap_up(int F)
{
	int T,aux;
	for(;;)
	{
		T=F>>1;
		if(d[H[T]]<=d[H[F]])return;
		aux=H[T];H[T]=H[F];H[F]=aux;
		P[H[T]]=T;P[H[F]]=F;
		F=T;
	}
}

void heap_down(int T)
{
	int F,aux;
	for(;;)
	{
		F=T<<1;
		if(F>L)return;
		if(F<L)
			if(d[H[F+1]]<d[H[F]])
				F++;
		if(d[H[F]]>=d[H[T]])return;
		aux=H[F];H[F]=H[T];H[T]=aux;
		P[H[T]]=T;P[H[F]]=F;
		T=F;
	}
}