#include<cstdio>
#include<utility>
#include<vector>
#include<algorithm>
#define HEAP make_heap(h+f+1,h+f+1,cmp)
using namespace std;
vector<pair<int,int> > v[50010];
void read(),solve();
int n,m,A,B,C,f,D,N,d[50010],oo=500000000,h[50010],i,cmp(int I,int J);
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()
{
	vector<pair<int,int> >::iterator it;
	for(i=2;i<=n;i++)
	{
		d[i]=oo;h[i]=i;
	}
	h[1]=1;d[1]=0;
	for(f=1;f<=n;f++)
	{
		N=h[f];D=d[N];
		for(it=v[N].begin();it!=v[N].end();it++)
		{
			if(D+it->second<d[it->first])
				d[it->first]=D+it->second;
		}
		HEAP;
	}
	for(i=2;i<=n;i++)
		printf("%d ",d[i]); 
}
int cmp(int I,int J)
{
	return d[I]<=d[J];
}