#include "pch.h"
#include <iostream>
#include <limits.h> 
#include <fstream>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int minDistance(int dist[], bool verificat[], int n)
{
	int min = INT_MAX, min_index;
	for (int v = 1; v <= n; v++)
		if (verificat[v] == false && dist[v] < min)
			min = dist[v], min_index = v;
	return min_index;
}

int main()
{
	int n, m;
	f >> n >> m;
	int graph[40][40];
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
		{
			graph[i][j]=0;
		}
	int n1, n2, c;
	for (int i = 0; i < m; i++)
	{
		f >> n1 >> n2 >> c;
		graph[n1][n2] = c;
	}

	int dist[40];
	bool verificat[40];
	for (int i = 1; i <= n; i++)
		dist[i] = INT_MAX, verificat[i] = false;
	dist[1] = 0;
	for (int count = 0; count < n - 1; count++)
	{
		int u = minDistance(dist, verificat, n);
		verificat[u] = true;
		for (int v = 1; v <= n; v++)
			if (!verificat[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) 
				dist[v] = dist[u] + graph[u][v];
	}
	for (int i = 2; i <= n; i++)
		g << dist[i] << " ";
	g.close();
}