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

#define INF 10000000

vector <vector<pair<int, int> > > G;

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

void Read();
void Dijkstra();

int n, m;
int d[50001];

queue <int> Q;

int main()
{
	Read();
	Dijkstra();
	
	for (int i = 2; i <= n; ++i)
		if (d[i] != INF)
			fout << d[i] << ' ';
		else
			fout << 0 << ' ';
	fout << '\n';
	
	fout.close();
	fin.close();
	return 0;
}

void Read()
{
	fin >> n >> m;
	G.resize(n+1);
	
	int x, y, c;
	for (int i = 1; i <= m; ++i)
	{
		fin >> x >> y >> c;
		G[x].push_back(make_pair(y, c));
	}
	
	for (int i = 2; i <= n; ++i)
		d[i] = INF;
}

void Dijkstra()
{
	Q.push(1);
	
	while(!Q.empty())
	{
		int k = Q.front();
		Q.pop();
		
		for (int i = 0; i < (int)G[k].size(); ++i)
			if (d[G[k][i].first] > d[k] + G[k][i].second)
			{
				Q.push(G[k][i].first);
				d[G[k][i].first] = d[k] + G[k][i].second;
			}
	}
}