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

ofstream fout("dijkstra.out");
#define INF 0x3f3f3f

int n, m, d[50001];  // distanta la nodul sursa la nodi i
vector<int> G[50001], C[50001]; // G - graful; C - matricea ponderilor

set< pair<int, int> > T;

void Read();
void Dijkstra(int src);
void Write();
int main()
{
	Read();
	Dijkstra(1);
	Write();
	fout.close();
	return 0;
	
}

void Read()
{
	ifstream fin("dijkstra.in");
	fin >> n >> m;
	int a, b, c;
	for ( ; m; --m )
	{
		fin >> a >> b >> c;
		G[a].push_back(b);
		C[a].push_back(c);
	}
	fin.close();
}

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

void Write()
{
	for ( int i = 2; i <= n; ++i )
		fout << (d[i] == INF ? 0 : d[i]) << ' ';
}