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

struct n_farther
{
	bool operator() (nod a, nod b)
	{
		return a.dis>b.dis;
	}
};

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;
	static bool viz[_NM];
	priority_queue<nod,vector<nod>,n_farther> pq;
	nod tmp; tmp.i=1; tmp.dis=0;
	pq.push(tmp);
	while (!pq.empty())
	{
		int cur=pq.top().i; pq.pop();
		viz[cur]=1;
		for (vector<muchie>::iterator it=vAd[cur].begin();it!=vAd[cur].end();++it)
		{
			if (viz[it->des]) continue;
			if (dist[cur]+it->w < dist[it->des])
			{
				dist[it->des]=dist[cur]+it->w;
				nod tmp;
				tmp.i=it->des; tmp.dis=dist[it->des];
				pq.push(tmp);
			}
		}
	}
	for (int i=2;i<=nN;i++)
		fout<<(dist[i]==INF ?0:dist[i])<<' ';
	return 0;
}