#include<fstream>
#include<iostream>
#include<vector>
#define nmax 50003
#define maxx 999999999

using namespace std;

int heap[nmax], d[nmax], poz[nmax], n, m, nh;

vector < pair<int, int> >  l[nmax];

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



void read()
{
	int i, x, y, c;

	fin >> n >> m;

	for (i = 1; i <= m; i++)
	{
		fin >> x >> y >> c; 

		l[x].push_back(make_pair(y, c));

	}
}




void swap(int i, int j)
{
	int aux;

	aux = heap[i];
	heap[i] = heap[j];
	heap[j] = aux;

	poz[heap[i]] = i;
	poz[heap[j]] = j;
}




void heapup(int k)
{
	if (k <= 1)
		return;

	int f = k / 2;

	if (d[heap[k]] < d[heap[f]])
	{
		swap(f, k);
		heapup(f);
	}

}





void heapdw(int k)
{
	int i = 2 * k;

	if (i <= nh)
	{
		if (i + 1 <= nh && d[heap[i + 1]] < d[heap[i]])
			i++;

		if (d[heap[i]] < d[heap[k]])
		{
			swap(i, k);
			heapdw(i);
		}

	}
}




int out_from_heap()
{
	swap(1, nh);
	poz[heap[nh]] = 0;
	nh--;

	return heap[nh + 1];
}




void dijkstra(int r)
{
	int i, p;

	for (i = 1; i <= n; i++)
	{
		d[i] = maxx;
		heap[i] = i;
		poz[i] = i;
	}

	d[r] = 0;
	nh = n;

	while (nh > 0)
	{
		p = out_from_heap(); 
		heapdw(1);


		for (i = 0; i < l[p].size(); i++)
		{
	
			if (d[l[p][i].first] > d[p] + l[p][i].second && poz[l[p][i].first])
			{
				d[l[p][i].first] = d[p] + l[p][i].second;

				heapup(poz[l[p][i].first]);
			}
		}
	}

}



void afis()
{
	int i;

	for (i = 2; i <= n; i++)
		if (d[i] < maxx)
			fout << d[i] << " ";
		else
			fout << "0 ";
}




int main()
{
	read();

	dijkstra(1);

	afis();

	fin.close();
	fout.close();

	return 0;
}