#include <fstream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");

const int Nmax = 50001;
const int oo = 0x3f3f3f3f;

vector < pair <int, int> > a[Nmax];
queue <int> Q;

int n, m, i, j, x, y, c, d[Nmax], xc, xi;
char parser[20];

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

int main()
{
	fin >> n >> m; fin.get();
	for (i=1; i<=m; i++)
	{
		fin.getline (parser, 20);
		x=y=c=j=0;
		while (parser[j]!=' ')
		{
			x=x*10+parser[j]-'0';
			++j;
		}
		++j;
		while (parser[j]!=' ')
		{
			y=y*10+parser[j]-'0';
			++j;
		}
		++j;
		while (parser[j])
		{
			c=c*10+parser[j]-'0';
			++j;
		}
		a[x].push_back(make_pair(y, c));
	}
	memset (d, oo, sizeof d);
	BFS (1);
	for (i=2; i<=n; i++)
	{
		if (d[i]<oo) fout << d[i] << " ";
		else fout << "0 ";
	}
}