#include<cstdio>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;

int i,j,n,m,x,y,z,gata[50001],dMin[50001],nod;
vector <int> G[50001], cost[50001];
set < pair<int,int> > S;
pair <int,int> aux;

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		G[x].push_back(y);
		cost[x].push_back(z);
	}
	for(i=2;i<=n;i++)
		dMin[i]=10000000;
	nod=1;
	
	S.insert(make_pair(0,1));
	for(i=2;i<=n;i++)
		S.insert(make_pair(10000000,i));
		
	while(gata[0]!=n)
	{	
		for(i=0;i<G[nod].size();i++)
		{
			if(dMin[G[nod][i]]>dMin[nod]+cost[nod][i])
			{
				S.erase(make_pair(dMin[G[nod][i]],G[nod][i]));
				dMin[G[nod][i]]=dMin[nod]+cost[nod][i];
				aux=make_pair(dMin[G[nod][i]],G[nod][i]);
				S.insert(aux);
			}
		}
		gata[nod]=1;
		S.erase(make_pair(dMin[nod],nod));
		gata[0]++;
		nod=S.begin()->second;
	
	}
	for(i=2;i<=n;i++)
		if(dMin[i]==10000000)
			printf("0 ");
		else
			printf("%d ",dMin[i]);
	return 0;
}