#include<cstdio>
#include<vector>
#include<utility>
#define NMAX 50010
#define oo 999999999
using namespace std;
vector<pair<int,int> >V[50010];
void read(),solve(),HeapUp(int),HeapDown();
int a,b,c,m,n,curr,H[NMAX],cost[NMAX],poz[NMAX],i,nn;
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(;m;m--)
	{
		scanf("%d%d%d",&a,&b,&c);
		V[a].push_back(make_pair(b,c));
	}
}
void solve()
{
	for(i=1;i<=n;i++){H[i]=i;cost[i]=oo;poz[i]=i;}
	cost[1]=0;
	for(nn=n;nn;)
	{
		curr=H[1];
		for(vector<pair<int,int> >::iterator it=V[curr].begin();it!=V[curr].end();it++)
		{	
			if(cost[it->first]>cost[curr]+it->second)
			{
				cost[it->first]=cost[curr]+it->second;
				HeapUp(it->first); //hip-hop:)))))))))
			}
		}
		poz[H[nn]]=1;
		H[1]=H[nn];
		--nn;
		HeapDown();
	}
	for(i=2;i<=n;i++)if(cost[i]==oo)printf("0 "); else printf("%d ",cost[i]);
}
void HeapUp(int X)
{
	int aux,cn;
	for(int cnt=poz[X];cnt>1;)
	{
		cn=cnt>>1;
		if(cost[H[cnt]]<cost[H[cn]])
		{
			poz[H[cn]]=cnt;
			poz[H[cnt]]=cn;
			aux=H[cnt];
			H[cnt]=H[cn];
			H[cn]=aux;
			cnt=cn;
			continue;
		}
		return;
	}
}
void HeapDown()
{
	int aux,cn;
	for(int cnt=1;;)
	{
		cn=cnt<<1;
		if(cn>nn)return;
		if(cn<nn)
			if(cost[H[cn+1]]<cost[H[cn]])++cn;
		if(cost[H[cnt]]<=cost[H[cn]])return;
		aux=H[cnt];H[cnt]=H[cn];H[cn]=aux;
		poz[H[cnt]]=cnt;poz[H[cn]]=cn;
		cnt=cn;
	}
}