#include<cstdio>
#include<vector>
#include<queue>
using namespace std;

struct vertex
{
	int x; int cost;
};

queue<int> q;
vector <vertex> G[50001];

int n,m,i,j,d[50001],a,viz[50001];

int dijkstra()
{
	q.push(1);
	viz[1]=1;
	while(!q.empty())
	{
		int nod=q.front();
		for(i=0;i<G[nod].size();i++)
			if(d[nod]+G[nod][i].cost<d[G[nod][i].x])
			{
				d[G[nod][i].x]=d[nod]+G[nod][i].cost;
				if(viz[G[nod][i].x]==0)
					q.push(G[nod][i].x);
				viz[G[nod][i].x]=1;
			}
		q.pop();
		viz[nod]=0;
	}
	return 0;
}
	
	
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d%d",&n,&m);
	vertex nod;
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&a,&nod.x,&nod.cost);
		G[a].push_back(nod);
	}
	for(i=2;i<=n;i++)
		d[i]=250000010;
	dijkstra();
	for(i=2;i<=n;i++)
		printf("%d ",d[i]);
	return 0;
}