#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
vector<int> v[50001],vc[50001];
struct eu{int x,y;};
eu nod;
priority_queue<pair<int,int > > pq;
int n,m,i,j,k,x,y,val,vec[50001];
int main ()
{
freopen("dijkstra.in","r",stdin);
freopen("dijkstra.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=2;i<=n;i++)
	vec[i]=1000000000;
for(i=1;i<=m;i++)
	{
	scanf("%d%d%d",&x,&y,&val);
  v[x].push_back(y);
  vc[x].push_back(val);
	}
pq.push(make_pair(0,1));
while(!pq.empty())
  {
	int pp=0;
	if(pq.top().first==vec[pq.top().second])
		{
		pp=1;
		nod.x=pq.top().first;
		nod.y=pq.top().second;
		pq.pop();
		for(i=0;i<v[nod.y].size();i++)
			if(vec[v[nod.y][i]]>vec[nod.y]+vc[nod.y][i])
				{
				vec[v[nod.y][i]]=vec[nod.y]+vc[nod.y][i];
				pq.push(make_pair(vec[v[nod.y][i]],v[nod.y][i]));
				}
		}
	if(pp==0)
		pq.pop();
  }
for(i=2;i<=n;i++)
	printf("%d ",vec[i]);
return 0;
}