#include<fstream>
#include<queue>
#define _NM 50010
#define INF 1073741823
using namespace std;
struct muchie
{
	int des,w;
};

int main()
{
	ifstream fin("dijkstra.in");
	ofstream fout("dijkstra.out");
	int nN, nM;
	fin>>nN>>nM;
	vector<muchie> vAd[_NM];
	for (int i=1;i<=nM;i++)
	{
		int nod; muchie tmp;
		fin>>nod>>tmp.des>>tmp.w;
		vAd[nod].push_back(tmp);
	}
	int dist[_NM]; dist[1]=0;
	for (int i=2;i<=nN;i++) dist[i]=INF;
	queue<int> q;
	q.push(1);
	while (!q.empty())
	{
		int cur=q.front(); q.pop();
		for (vector<muchie>::iterator it=vAd[cur].begin();it!=vAd[cur].end();++it)
			if (dist[cur]+it->w < dist[it->des])
			{
				dist[it->des]=dist[cur]+it->w;
				q.push(it->des);
			}
	}
	for (int i=2;i<=nN;i++)
		fout<<(dist[i]==INF ?0:dist[i])<<' ';
	return 0;
}