#include<fstream>
#include<vector>
using namespace std;
const int MAXN=50010;
const int INF=10000000;
int n,m,qsize;
int q[MAXN],d[MAXN],poz[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[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[i],poz[smallest]);
		min_heapify(smallest);
	}
}
int extract_min()
{
	int minim=q[1];
	poz[q[1]]=-1;
	poz[q[qsize]]=1;
	q[1]=q[qsize];
	q[qsize]=0;
	--qsize;
	min_heapify(1);
	return minim;
}
void schimba_poz(int i)
{
	while (d[q[i]]<d[q[parent(i)]] && i>1)
	{
		swap(q[i],q[parent(i)]);
		swap(poz[q[i]],poz[q[parent(i)]]);
		i=parent(i);
	}
	min_heapify(i);
}
void relax(int u,pair<int,int> v)
{
	if (d[u]+v.second<d[v.first])
	{
		d[v.first]=d[u]+v.second;
		schimba_poz(poz[v.first]);
	}
}
void dijkstra()
{
	int i,u;
	for (i=2;i<=n;++i)
	{
		q[i]=i;
		poz[i]=i;
		d[i]=INF;
	}
	q[1]=1;
	poz[1]=1;

	while (qsize)
	{
		u=extract_min();
		for (vector<pair<int,int> >::iterator it=adj[u].begin();it!=adj[u].end();++it)
		{
			relax(u,*it);
		}
	}

}

void citire()
{
	int i,x,y,w;
	ifstream fin("dijkstra.in");
	fin>>n>>m;	qsize=n;
	for (i=1;i<=m;++i)
	{
		fin>>x>>y>>w;
		adj[x].push_back(make_pair(y,w));
	}
	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();
}
int main()
{
	citire();
	dijkstra();
	afisare();
	return 0;
}