#include <fstream>
#include <vector>
#include <set>
using namespace std;

#define INF 10000000

vector <int> G[50001], C[50001];
set <pair<int, int> > T;

int n, m;

int d[50001];

void Dijkstra();
void Read();
void Write();

int main()
{
	Read();
	Dijkstra();
	Write();
	return 0;
}

void Read()
{
	ifstream fin("dijkstra.in");
	fin >> n >> m;
	
	int x, y, c;
	
	while(fin >> x >> y >> c)
	{
		G[x].push_back(y);
		C[x].push_back(c);
	}
	fin.close();
}

void Dijkstra()
{
	for (int i = 2; i <= n; ++i)
		d[i] = INF;
	T.insert(make_pair(0,1));
	
	int val, x;
	
	while((int)T.size() > 0)
	{
		val = (*T.begin()).first;
		x = (*T.begin()).second;
		T.erase(*T.begin());
		for (int i = 0; i < (int)G[x].size(); ++i)
		{
			if (d[G[x][i]] > C[x][i] + val)
				d[G[x][i]] = C[x][i] + val;
			T.insert(make_pair(d[G[x][i]], G[x][i]));
		}
	}
}

void Write()
{
	ofstream fout("dijkstra.out");
	for (int i = 2; i <= n; ++i)
	{
		if (d[i] != INF)
			fout << d[i] << ' ';
	}
	fout.close();
}