#include<fstream>
#include<vector>
using namespace std;
const int MAXN=50010;
const int INF=1000000000;

int qsize,n,m;
int q[MAXN],d[MAXN],poz[MAXN];
struct edge
{
	int src,dest,cost;
};
vector<edge> adj[MAXN];

void citire()
{
	int i;
	edge muchie;
	ifstream fin("dijkstra.in");
	fin>>n>>m;	qsize=n;
	for (i=1;i<=m;++i)
	{
		fin>>muchie.src>>muchie.dest>>muchie.cost;
		adj[muchie.src].push_back(muchie);
	}
	fin.close();
}
void afisare()
{
	ofstream fout("dijkstra.out");
	for (int i=2;i<=n;++i)
	{
		if (d[i]==INF)
			fout<<0<<' ';
		else
			fout<<d[i]<<' ';
	}
	fout.close();
}
void init()
{
	int i;
	for (i=1;i<=n;++i)
	{
		q[i]=poz[i]=i;
		d[i]=INF;
	}
	d[1]=0;
}

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 up_heap(int i)
{
	while (d[q[i]]<d[q[parent(i)]])
	{
		swap(q[i],q[parent(i)]);
		swap(poz[q[i]],poz[q[parent(i)]]);
		i=parent(i);
	}
}
void down_heap(int i)
{
	int smallest=i,l=left(i),r=right(i);
	if (l<=qsize && d[q[l]]<d[q[smallest]])
		smallest=l;
	if (r<=qsize && d[q[r]]<d[q[smallest]])
		smallest=r;
	if (smallest!=i)
	{
		swap(q[i],q[smallest]);
		swap(poz[q[i]],poz[q[smallest]]);
		down_heap(smallest);
	}
}
int extract_min()
{
	int minim=q[1];
	q[1]=q[qsize];
	poz[q[qsize]]=1;
	--qsize;
	down_heap(1);
	return minim;
}
void relax(edge e)
{
	if (d[e.src]+e.cost<d[e.dest])
	{
		d[e.dest]=d[e.src]+e.cost;
		up_heap(poz[q[e.dest]]);
	}
}
void dijkstra()
{
	int i,u;
	while (qsize)
	{
		u=extract_min();
		for(vector<edge>::iterator it=adj[u].begin();it!=adj[u].end();++it)
		{
			relax(*it);
		}
	}
}
int main()
{
	citire();
	init();
	dijkstra();
	afisare();
	return 0;
}