#include <fstream>
#include <vector>
#include <utility>
#define MAXN 50010
using namespace std;
vector<pair<int,int> > v[MAXN];
int n,m,h,u,heap[MAXN],p[MAXN],dist[MAXN];
void urca(int x)
{
	int key=heap[x];
	while(x>1 and dist[heap[x/2]]<dist[key])
	{
		heap[x]=heap[x/2];
		p[heap[x/2]]=x;
		x=x/2;		
	}
	heap[x]=key;
	p[key]=x;		
}
void coboara(int x)
{
	int minim=x;
	if(2*x<=h and dist[heap[2*x]]<dist[heap[minim]]) minim=2*x;
	if(2*x+1<=h and dist[heap[2*x+1]]<dist[heap[minim]]) minim=2*x+1;
	if(minim!=x)
	{
		swap(heap[x],heap[minim]);
		swap(p[x],p[minim]);
		coboara(minim);
	}
}
int extract()
{
	swap(heap[1],heap[h]);
	swap(p[heap[1]],p[heap[h]]);
	h--;
	coboara(1);
	return heap[h+1];	
}
int main()
{
	int i,x,y,c;
	ifstream fi("dijkstra.in");
	ofstream fo("dijkstra.out");
	fi>>n>>m;
	for(i=1;i<=m;i++)
	{
		fi>>x>>y>>c;
		v[x].push_back(make_pair(y,c));
	}
	for(i=1;i<=n;i++)
	{
		heap[i]=i;
		p[i]=i;
		dist[i]=int(2e9);
	}
	h=n;
	dist[1]=0;
	while(h)
	{
		u=extract();
		for(i=0;i<v[u].size();i++)
		if(dist[v[u][i].first]>dist[u]+v[u][i].second)
		{
			dist[v[u][i].first]=dist[u]+v[u][i].second;
			urca(v[u][i].first);
		}		
	}
	for(i=2;i<=n;i++) fo<<dist[i]<<" ";
	fo<<"\n";
	return 0;
}