Задача Schools. У нашому районі n сіл, деякі з них з’єднані дорогами, що ніде не перетинаються. У кожному селі одна школа. Директор департаменту освіти отримав наказ, згідно якого з метою економії в районі повинна залишитись лише одна школа, а з інших шкіл учнів возитимуть шкільні автобуси. Райдержадміністрація виділяє один літр бензину на один кілометр на кожного учня. Директор знає, скільки учнів навчається у кожній школі. Також відомі відстані між селами. Допоможіть визначити, яку школу потрібно залишити, щоб мінімізувати витрати бензину.
Технічні умови. Програма Schools читає з клавіатури цілі числа n (1<=n<=100) - кількість сіл, та через пропускm – кількість доріг. Далі програма читає через пропуск m трійок чисел – номери сіл i, j (1<=i,j<=n, i<>j), що з’єднує дорога, та s – довжина дороги s (натуральне число, що не перевищує 100). Далі через пропуск програма читає n натуральних чисел ai, що не перевищують 100 – кількість учнів у і-й школі. Гарантується, що по дорогах можна проїхати між будь-якими двома селами. Будь-які два села з’єднані не більше ніж однією дорогою. Кожна дорога описується один раз. На всіх дорогах дозволяється рух у двох напрямках. Якщо кілька шкіл забезпечать мінімум витрат бензину, директор вибирає школу з найменшим номером.
Приклад
Введення
3 3 1 2 8 2 3 2 3 1 6 10 6 4
Виведення
1
Коментар. Якщо вибрати першу школу, треба 8*6+6*4=72, якщо другу – 8*10+2*4=88, якщо третю – 6*10+2*6=72 літрів бензину.