#include<cstdio>
#include<vector>
#include<utility>
#define NMAX 50010
#define oo 99999999
using namespace std;
vector<pair<int,int> >V[1001];
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;--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];
		HeapDown();
	}
	for(i=2;i<=n;i++)if(cost[i]==oo)printf("0 "); else printf("%d ",cost[i]);
}
void HeapUp(int X)
{
	int aux;
	for(int cnt=poz[X];cnt>1;cnt/=2)
	{
		if(cost[H[cnt]]<cost[H[cnt/2]])
		{
			poz[H[cnt/2]]=poz[H[cnt/2]]*2+poz[H[cnt]]%2;
			poz[H[cnt]]/=2;
			aux=H[cnt];
			H[cnt]=H[cnt/2];
			H[cnt/2]=aux;
			continue;
		}
		break;
	}
}
void HeapDown()
{
	int aux;
	for(int cnt=1;cnt*2<=nn;)
	{
		if(cost[H[cnt]]>cost[H[cnt*2+1]]&&cost[H[cnt*2]]>cost[H[cnt*2+1]]&&cost[H[cnt*2+1]])
		{
			poz[H[cnt]]=poz[H[cnt]]*1+1;
			poz[H[cnt*2+1]]/=2;
			aux=H[cnt];
			H[cnt]=H[cnt*2+1];
			H[cnt*2+1]=aux;
			cnt=cnt*2+1;
			continue;
		}
		if(cost[H[cnt]]>cost[H[cnt*2]])
		{
			poz[H[cnt]]*=2;
			poz[H[cnt*2]]/=2;
			aux=H[cnt];
			H[cnt]=H[cnt*2];
			H[cnt*2]=aux;
			cnt*=2;
			continue;
		}
		break;
	}
}