#include<cstdio>
#include<vector>
#include<queue>
#include<fstream>
#define N 50002
#define X 50000001
using namespace std;
vector <int> a[N], cost[N];
priority_queue<pair <int,int>,vector<pair<int,int> >, greater<pair<int,int> > > h;
int d[N],pred[N],n,m;
void citire();
void afis();
void dijkstra(int);
bool s[N];
void extinde(int,int);

ifstream in("dijkstra.in");

int main()
{
//	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	citire();
	dijkstra(1);
	afis();
	return 0;
}
void citire()
{
	int x,y,c;
	//scanf("%d%d",&n,&m);
	in>>n>>m;
	while(m)
	{
		m--;
		in>>x>>y>>c;
		a[x].push_back(y);
		cost[x].push_back(c);
	}
}
void dijkstra(int x)
{
	int i,c;
	for(i=1;i<=n;++i)
		d[i]=X;
	d[x]=0;
//	s[x]=true;
	h.push(make_pair(0,x));
	while(!h.empty())
	{
		x=h.top().second;
		c=h.top().first;
		h.pop();
		if(s[x])
			continue;
		s[x]=true;
		extinde(x,c);
	}
}
void extinde(int x,int c)
{
	int y=0,c1=0;
	size_t g=a[x].size();
	for(size_t i=0;i<g;++i)
	{
		y=a[x][i];
		c1=cost[x][i];
		if(c+c1<d[y])
		{
			d[y]=c+c1;
			h.push(make_pair(d[y],y));
			pred[y]=x;
		}
	}
}
void afis()
{
	int i;
	for(i=2;i<=n;++i)
		if(d[i]!=X)
			printf("%d ",d[i]);
		else
			printf("0 ");
}