#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const char iname[] = "dijkstra.in";
const char oname[] = "dijkstra.out";

ifstream fin(iname);
ofstream fout(oname);

int d[50005];

struct cmp
{
	bool operator()(int &x, int &y)const
	{
		if(d[x] > d[y])
			return 0;
		return 1;
	}
};

priority_queue<int, vector<int>, cmp> Q;
vector< pair <int, int> > gr[50005];
int n, m, i, c, x, y;

void init()
{
	for(int i = 1; i <= n; i ++)
		d[i] = 29102011;
}


void dijkstra()
{	
	int vf;
	d[1] = 0;
	Q.push(1);
	while(!Q.empty())
	{
		vf = Q.top();
		Q.pop();
		for(vector<pair <int, int> >::iterator it = gr[vf].begin(); it != gr[vf].end(); ++ it)
		{
			if(d[it->first] > it -> second + d[vf])
			{
				d[it->first] = it -> second + d[vf];
				Q.push(it -> first);
			}
		}
	}
}
	


int main()
{
	fin >> n >> m;
	for(i = 1; i <= m; i ++)
	{
		fin >> x >> y >> c;
		gr[x].push_back(make_pair(y, c));
	}
	init();
	dijkstra();
	for(i = 1; i <= n; i ++)
		if(d[i] == 29102011)
			d[i] = 0;
	for(i = 2; i <= n; i ++)
		fout << d[i] << " ";
	return 0;
}