#include<fstream>
#include<vector>
using namespace std;
const int MAXN=50010;
const int INF=10000000;
int n,m,qsize;
int d[MAXN];		//distanta sau costul
int q[MAXN];		//min-priority queue-ul sortat dupa d[q[i]]
bool in[MAXN];
vector< pair<int,int> > adj[MAXN];



inline int parent(int i){return i>>1;}
inline int left(int i){return i<<1;}
inline int right(int i){return (i<<1)+1;}

void min_heapify(int i)
{
	int smallest=i,l=left(i),r=right(i);
	if (l<=qsize && d[l]<d[smallest])
		smallest=l;
	if (r<=qsize && d[r]<d[smallest])
		smallest=r;
	if (smallest!=i)
	{
		swap(q[smallest],q[i]);
		min_heapify(smallest);
	}
}
void insert(int i)
{
	++qsize;
	q[qsize]=i;
	i=qsize;
	while(d[q[i]]<d[q[parent(i)]])
	{
		swap(q[i],q[parent(i)]);
		i=parent(i);
	}
}
void extract_min(int& minim)
{
	minim=q[1];
	q[1]=q[qsize];
	q[qsize]=0;
	--qsize;
	in[minim]=false;
	min_heapify(1);
}
void relax(int u,pair<int,int> v)
{
	if (d[u]+v.second<d[v.first])
	{
		d[v.first]=d[u]+v.second;
		if (!in[v.first])	//daca nu e in coada il mai inserez odata
			insert(v.first);
	}
}
void citire()
{
	int i,x,y,cost;
	ifstream fin("dijkstra.in");
	fin>>n>>m;
	for (i=1;i<=m;++i)
	{
		fin>>x>>y>>cost;
		adj[x].push_back(make_pair(y,cost));
	}
	for (i=1;i<=n;++i)
	{
		q[i]=i;
		d[i]=INF;
		in[i]=true;
	}
	d[1]=0;
	qsize=n;
	fin.close();
}
void dijkstra()
{
	int u;
	while (qsize)
	{
		extract_min(u);
		for (vector<pair<int,int> >::iterator it=adj[u].begin();it!=adj[u].end();++it)
		{
			relax(u,*it);
		}
	}
}
void afisare()
{
	ofstream fout("dijkstra.out");
	for (int i=2;i<=n;++i)
		fout<<d[i]<<' ';
	fout<<'\n';
	fout.close();
}
int main()
{
	citire();
	dijkstra();
	afisare();
	return 0;
}