графы

Условие
Вводится число N – количество домиков и число К – количество дорог. Домики пронумерованы числами от 1 до N. Каждая дорога определяется тройкой чисел: двумя номерами домиков, которые являются концами этой дороги, и длиной дороги (длины дорог - положительные целые числа). В каждом домике живет по одному человеку.

Необходимо найти точку (место встречи всех людей), от которой суммарное расстояние до всех домиков будет минимальным. Если точка лежит на дороге, то указать номера домиков, которые являются концами этой дороги, и расстояние от первого из этих домиков. Если точка совпадает с домиком, то указать его номер.

Входные данные
Входные данные находятся в файле input.in.
Первая срока содержит количество домиков N и количество дорог M.
Затем идут M строк файла по три числа в каждой, которые задают дороги: номера домиков, которые являются концами дороги, и длина дороги.

Выходные данные

Выходные данные находятся в файле output.out, который содержит одну строку. Если точка встречи лежит на дороге, то строка содержит три числа: номера конечных домиков этой дороги и расстояние от первого из этих домиков до этой точки. Если точка совпадает с домом, то строка выходного файла содержит номер этого домика и суммарное расстояние от всех домиков до этого домика. Все числа в строках файлов разделены одним или несколькими пробелами.

Пример
input.in
6 9
1 2 2
2 3 3
3 4 15
4 5 5
5 6 6
6 1 20
1 3 7
3 6 5
4 6 8
output.out
3 37

0