#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
queue <int> Q;
vector <int> G[50001],cost[50001];
int n,m,i,j,viz[50001],cos[50001],l,x,y,c;

int bfs(int nod)
{
	int i=0,j;
	l=1;
	cos[nod]=0;
	Q.push(nod);
	viz[nod]=1;
	while(Q.size()>0)
	{
		i++;
		for(j=0;j<G[Q.front()].size();j++)
		{
			if(cos[G[Q.front()][j]]>cos[Q.front()]+cost[Q.front()][j])
			{
				if(viz[G[Q.front()][j]]==0)
					Q.push(G[Q.front()][j]);
				cos[G[Q.front()][j]]=cos[Q.front()]+cost[Q.front()][j];
				viz[G[Q.front()][j]]=1;
			}
		}
		viz[i]=0;
		Q.pop();
	}
		return 0;
}
	
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,&c);
		G[x].push_back(y);
		cost[x].push_back(c);
	}
	for(i=1;i<=n;i++)       
		cos[i]=999999999; 
	bfs(1);
	for(i=2;i<=n;i++)
		printf("%d ",cos[i]);
	return 0;
}