#include <algorithm>
#include <vector>
#include <fstream>
#include <cmath>

#include <iomanip>

#include <queue>

#include <tuple>

#include <limits>

#include <stdio.h>

#include <string.h>

#include <string>

using namespace std;



ifstream fin("dijkstra.in");

ofstream fout("dijkstra.out");



#define INF 9223372036854775807



bool processed[100000];

long long dist[100000];

vector<tuple<int, int> >vp[100000];


void dijkstra(int k, int n)

{

	for (int i = 0; i <= n; i++)

		dist[i] = INF;



	priority_queue<pair<int, int> >pq;

	pq.push({ 0,k });

	dist[k] = 0;

	while (!pq.empty())

	{

		k = pq.top().second;

		pq.pop();

		if (processed[k])continue;

		processed[k] = 1;

		for (auto u : vp[k])

		{

			int b, w;

			tie(b, w) = u;

			if (dist[k] + w < dist[b])

			{

				dist[b] = dist[k] + w;

				pq.push({ -dist[b], b });

			}



		}

	}

}





int main()

{

	int n, m;

	fin >> n >> m;

	for (int i = 0; i < m; i++)

	{

		int a, b, w;

		fin >> a >> b >> w;

		vp[a].push_back({ b,w });

	}



	dijkstra(1, n);

	for (int i = 2; i <= n; i++) {

		if (dist[i] != INF)

			fout << dist[i] << ' ';

		else fout << 0 << ' ';

	}



}