//https://infoarena.ro/problema/dijkstra
//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("fast-math")
//#pragma GCC optimize ("unroll-loops")
#include <iostream>
#include <fstream>
#include <vector>
#include <climits>
using namespace std;

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

vector <vector<pair<int, int>>> gr;
// first pana unde, second distanta
int main()
{
	/*ios_base::sync_with_stdio(false);
	cin.tie(NULL);*/
	int n, m, x, y, d, i, j;

	fin >> n >> m;
	//cout << n << m << "\n";
	gr.resize(n + 1);
	for (i = 0; i < m; ++i)
	{
		fin >> x >> y >> d;
		//cout << x << " " << y << "\n";
		gr[x-1].emplace_back(y-1, d);
	}

	vector <int> dist(n+1, INT_MAX);
	vector <bool> fr(n+1, false);
	int mind, mini, cost, dir;
	dist[0] = 0;

	for (i = 0; i < n-1; ++i)
	{
		//cout << i << " ";
		mind = INT_MAX;
		mini = 0;
		for (j = 0; j < n; ++j)
		{
			if (!fr[j] && dist[j] <= mind)
			{
				mind = dist[j];
				mini = j;
			}
		}
		//cout << mini << " ";
		fr[mini] = true;
		for (const auto& x : gr[mini])
		{
			dir = x.first;
			cost = x.second;
			cout << dir << " " << cost << "\n";
			if (!fr[dir] && dist[mini] != INT_MAX && dist[mini] + cost < dist[dir])
			{
				dist[dir] = dist[mini] + cost;
			}
		}
	}
	for (i = 1; i < n; ++i)
	{
		if (dist[i] == INT_MAX)
		{
			fout << "0 ";
		}
		else
		{
			fout << dist[i] << " ";
		}
	}

	return 0;
}