Для того, чтобы делиться своими научными достижениями, ученые собираются на международные конференции. В том числе такие конференции проходят и у физиков-ядерщиков (и особенно популярны они начали становиться как-раз во времена Оппенгеймера).
Известно, что в каждом из $$$n$$$ городов проживает некоторое, возможно нулевое, количество ученых-ядерщиков. Между некоторыми городами мира можно добраться на некотором транспорте за определенную стоимость. В этот раз Роберту Оппенгеймеру, собирающему конференцию, придется подумать над менее научным вопросом: а как оптимальнее собрать всех ученых в одном городе?
Чтобы собрать всех ученых в одном городе, для тех из них, кто не проживает в городе проведения конференции, необходимо оплатить им билеты для перемещения из их родного города в город проведения. Разумеется, средства, выделенные на конференцию, хочется потратить на что-то более полезное, чем билеты, поэтому город для проведения конференции Роберт хочет выбрать так, чтобы минимизировать суммарные затраты на сборы ученых.
Помогите ему определить, какое минимальное количество денег придется потратить на покупку всех билетов для всех ученых, если пока еще не поздно выбрать любой город проведения.
В первой строке входных данных даны два целых числа $$$n$$$ и $$$m$$$ — количество городов и способов перемещений напрямую между парами городов ($$$1 \le n \le 250$$$; $$$n - 1 \le m \le 4 \cdot 10^4$$$).
Во второй строке даны $$$n$$$ чисел $$$c_i$$$ — количество ученых, проживающих в каждом из городов ($$$0 \le c_i \le 10^7$$$).
В следующих $$$m$$$ строках дано описание прямых маршрутов перемещений между городами. Описание каждого из них состоит из трех целых чисел $$$u_i$$$, $$$v_i$$$ и $$$w_i$$$ — пары номеров соединяемых городов и стоимости перемещения ($$$1 \le u_i, v_i \le n$$$; $$$u_i \ne v_i$$$; $$$1 \le w_i \le 10^7$$$).
Каждый описанный способ перемещения позволяет попасть из одного города в другой и наоборот. Гарантируется, что для любых двух городов есть не более одного способа переместиться между ними напрямую, но для любой пары городов есть хотя бы один (не обязательно прямой) маршрут между ними.
В первой и единственной строке выведите целое число — минимальное количество денег, которое потребуется придется потратить на покупку всех билетов для всех ученых.
4 41 2 2 31 2 31 3 12 3 62 4 1
14
5 81 3 1 1 22 5 54 5 104 3 33 2 62 1 55 1 63 5 24 2 10
28