Амин и Мурад решили создать игровой сервер "Майнкрафт". На свою грандиозную церемонию открытия они пригласили гостей. Приглашенные гости живут в разных городах и при соединении к серверу (в зависимости от местоположения) будут иметь определенную задержку (ping). Амин и Мурад осознав потенциальную проблему решили выбрать самое оптимальное местоположение для сервера.
Есть городов пронумерованных от до и двухсторонних каналов передачи между этими городами. Подключиться к серверу можно только через эти каналы. Посредством этих каналов можно создать сообщение между любыми двумя городами. Однако, никакие два города не могут иметь больше одного напрямую соединяющего их канала и ни один город не имеет каналов, соединяющих город к самому себе. Для каждого канала так же дается время задержки . И так, время задержки соединения от какого-либо города к серверу равняется наименьшей сумме задержек каналов на пути от этого города к серверу среди всех возможных путей.
Амин и Мурад хотят выбрать для сервера такой город, чтобы при соединении суммарная задержка соединений всех гостей была минимальной. Если сервер находится в городе в котором живет кто-либо из гостей, то задержка соединения для этого гостя будет равна .
Если можно выбрать несколько городов с минимальной суммарной задержкой, то Амин и Мурад выберут город с наименьшим номером. Необходимо найти город, который выберут Амин и Мурад и суммарную задержку соединения всех гостей к серверу.
В первой строке даны три целых числа — количество городов, каналов передачи и гостей соответственно. Во второй строке даны разных чисел — номера городов где живут гости. В каждой из последующих строк даны три целых числа . Этими числами обозначается двухсторонний канал между городами и с задержкой соединения .
Выведите два целых числа — номер города где будет находиться сервер и суммарная задержка соединения всех гостей к этому серверу.