Пожарное депо

Город обслуживается несколькими пожарными депо. Некоторые жители пожаловались, что расстояние от их дома до ближайшего пожарного депо достаточно велико и потребовали, чтобы было построено еще одно новое. Необходимо определить местоположение нового депо так, чтобы минимизировать расстояние от недовольных жителей до ближайших к ним депо.

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

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

Первая строка содержит два натуральных числа: f, количество существующих пожарных депо (f ≤ 100) и i, количество перекрестков (i ≤ 500). Перекрестки пронумерованы последовательно числами от 1 до i. Далее следует f строк, каждая из которых содержит номер перекрестка, на котором находится пожарное депо. Каждая из следующих строк состоит из трех натуральных чисел: первые два числа – номера перекрестков, которые соединены дорогой, а третье число – длина этой дороги. По всем дорогам можно двигаться в обоих направлениях, а между любыми двумя перекрестками существует путь.

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

Вывести следует одно число: наименьший номер перекрестка, на котором следует построить новое пожарное депо так, чтобы минимизировать наибольшее расстояние от любого перекрестка до ближайшего пожарного депо.