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

int dist[_NM];
struct n_closer
{
	bool operator() (int a, int b)
	{
		if (dist[a]==dist[b]) return a<b;
		return dist[a]<dist[b];
	}
};

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);
	}
	//dist[];
	for (int i=2;i<=nN;i++) dist[i]=INF;
	static bool viz[_NM];
	set<int,n_closer> pq;
	pq.insert(1);
	while (!pq.empty())
	{
		int cur=*pq.begin(); pq.erase(pq.begin());
		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])
			{
				pq.erase(it->des);
				dist[it->des]=dist[cur]+it->w;
				pq.insert(it->des);
			}
		}
	}
	for (int i=2;i<=nN;i++) fout<<dist[i]<<' ';
	return 0;
}