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

using namespace std;

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

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

int n, m, i, x, y, c;
int d[nmax], viz[nmax];

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

vector<pair <int, int> > Gr[nmax];
priority_queue<int, vector<int>, cmp> Q;

void dijkstra()
{	
	int i, x;
	Q.push(1);
	d[1] = 0;
	viz[1] = 1;
	for(i = 2; i <= n; i ++)
		d[i] = 218989982;
	while(!Q.empty())
	{
		x = Q.top();
		Q.pop();
		for(vector<pair <int, int> >::iterator it = Gr[x].begin(); it != Gr[x].end(); ++it)
		{
			if(!viz[it->first])
			{
				if(d[x] + it->second < d[it->first])
				{
					d[it -> first] = d[x] + it->second;
					viz[it -> first] = 1;
					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));
	}
	
	dijkstra();
	for(i = 2; i <= n; i ++)
	{
		if(d[i] == 218989982)
			fout << "0 ";
		else
			fout << d[i] << " ";
	}
	return 0;
}