#include <string>
#include <vector>
#include <fstream>
#include <sstream>
#include <iostream>
using namespace std;

#define INF 777 //деяке число для позначення безкінечності

typedef struct { //структура ребра
	int src, dest, weight;
} edge;

typedef struct { //структура графу
	int V, E;
	edge *arr;
} graph;
int a, b, c,
n,m,
total =0;
graph *newgraph(int V, int E) { //функція створення графу з V вершин і E ребер
	graph *current = (graph *)malloc(sizeof(graph));
	current->V = V;
	current->E = E;
	current->arr = (edge *)malloc(sizeof(edge)* E);
	return current;
}

int **adjmat(graph *g) { //функція створення матриці суміжності(функции c++ - шные)
	int **ret = new int*[g->V];
	for (int i = 0; i < (g->V); i++)
	{
		ret[i] = new int[g->V];
		for (int j = 0; j < (g->V); j++) {
			ret[i][j] = 0;
		}
	}
	for (int i = 0; i < (g->V); i++)
	{
		for (int j = 0; j < (g->V); i++)
			cout << ret[i][j] << " ";
		cout << endl;
	}
	for (int i = 0; i < g->E; i++) {
		int u = g->arr[i].src;
		int v = g->arr[i].dest;
		int w = g->arr[i].weight;
		ret[u][v] = w;
		ret[v][u] = w;
	}
	return ret;
}
void printPath(int parent[], int j) //вывод кратчайшего пути(хотя бы должен быть им)
{
	if (parent[j] == -1)
		return;

	printPath(parent, parent[j]);

	printf("%d ", j);
}



int *Dijkstra(int **GR, int V, int st) //функция с алгоритмом Дейкстры, возвращает массив с кратчайшими расстояниями
{
	int *distance, count, index, i, u;
	bool *visited;
	distance = new int[V];
	visited = new bool[V];
	for (i = 0; i<V; i++) { distance[i] = INF; visited[i] = false; }
	distance[st] = 0;
	for (count = 0; count<V - 1; count++)
	{
		int min = INF;
		for (i = 0; i<V; i++)
		if (!visited[i] && distance[i] <= min) { min = distance[i]; index = i; }
		u = index;
		visited[u] = true;
		for (i = 0; i<V; i++)
		if (!visited[i] && GR[u][i] && distance[u] != INF &&
			distance[u] + GR[u][i]<distance[i])
			distance[i] = distance[u] + GR[u][i];
	}
	int temp_i, temp = 0;
	for (int i = 0; i < V; i++) //выбор наименьшего веса из всех маршрутов
	{
		temp = distance[0];
		if (distance[i]>temp)
		{
			temp = distance[i];
			temp_i = i;
		}
	}
	int* path = new int;
	for (int i = 0; i < V; i++)
		path[i] = -1;
	printPath(path, temp_i); //вызов функции печати пути


	return distance;
}
void output(graph *&g) //функція створення файлу з вихідними даними(нужно, чтобы выводило путь с наименьшим весом )
{
	int **mat = adjmat(g);
	int* distance = Dijkstra(mat, g->V, 1);
	ofstream file;
	file.open("output.txt");
	if (!file.is_open())
	{
		cout << "Файл не удалось открыть" << endl;
		return;
	}
	else
	{
		for (int i = 0; i < g->V; i++)
		{
			file << distance[i];
			file << " ";
		}
	}

}

graph* input_data() //ввод данных с файла - первая строка - число вершин и ребер, дальше идут ребра с весами
{
	FILE* is;
	is = fopen("data.txt", "rt");
	fscanf(is, "%d%d", &n, &m);
	graph *g = newgraph(n, m ); //створення графу
	for (int i = 0; i < m; i++)
	{
		fscanf(is, "%d%d%d", &a, &b, &c);
		g->arr[i].src = a - 1;
		g->arr[i].dest = b - 1;
		g->arr[i].weight = c;
	}
	fclose(is);
	return g;
}
void main()
{

		graph* tree = input_data();
		//вызовы функций
		output(tree);

			system("pause");

}