#include <fstream>
#include <iomanip>
using namespace std;

ifstream is("dijkstra.in");
ofstream os("dijkstra.out");

const int INF = 0x3f3f3f3f;
const int Dim = 5001;

int c[Dim][Dim], n, m;    // c[i][j] - matricea ponderilor
int d[Dim];   // d[i] = dist minima de la sursa la nodul i
bool s[Dim];

void Read();
void Dijkstra(int x); // O(n^2)
void Write();

int main()
{
	Read();
	Dijkstra(1);

	Write();
	is.close();
	os.close();
	return 0;
}


// O(n * log m)
void Dijkstra(int x) // O(n^2)
{
	s[x] = true; d[x] = 0;
	for (int i = 1; i <= n; ++i)
		d[i] = c[x][i];
	int k, dmin;
	for (int pas = 1; pas <= n - 1; ++pas)
	{
		dmin = INF;
		for (int i = 1; i <= n; ++i)
			if ( !s[i] && d[i] < dmin)
				dmin = d[i], k = i;
		s[k] = true;
		for (int i = 1; i <= n; ++i)
			if ( !s[i] && d[i] > d[k] + c[k][i])
				d[i] = d[k] + c[k][i];
	}
}

void Read()
{
	is >> n >> m;
	for(int i = 1; i <=n; ++i)
		for(int j = 1; j <= n; ++j)
		{
			if(i != j)
				c[i][j] = INF;
		}
	int x, y, cost;
	while ( is >> x >> y >> cost )
	{
		c[x][y] = cost;
	}
}

void Write()
{
	for ( int i = 2; i <= n; i++ )
		os << d[i] << ' ';
}