Операція "Стейк чи кип`ятіння"
Маркетологи компанії "std::steak" розробили новий рекламний проект "Стейк чи кип'ятіння". Суть проекту полягає у захоплені ринку усієї Берляндії. Групи агентів будуть заходити у кожен будинок кожного міста і задавати безглузде запитанняч: "Стейк чи кип'ятіння?". Таким чином компанія розраховує повністю повергнути в жах усіх конкурентів і озадачити потенційних покупців.
Висадка груп агентів відбудеться у деяких містах Берляндії з повітря. Далі по дорогам агенти повинні відвідати усі міста країни. Міста з'єднані односторонніми дорогами, для кожної дороги задана її довжина. У кожному місті групи можуть ділится довільним чином (кількість людей у групі спочатку назвичайно велика).
Відомо, що витрати на переміщення по дорозі рівні її довжині. Для кожного міста відома вартість організації висадки десанту у нього.
Який найменший бюджет може мати операція "Стейк чи кип'ятіння"?
Вхідні дані
Вхідний файл складається з одного чи декількох наборів вхідних даних.
У першому рядку кожного набору записана пара цілих чисел N, M (1 ≤ N ≤ 300, 0 ≤ M ≤ N^2-N), де N - кількість міст у Берляндії, а M - кількість доріг. У другому рядку записана послідовність A_1, A_2, ..., A_N, де A_i- вартість висадки десанту в пукт i (1 ≤ A_i ≤ 1000). Далі в M рядках описано дороги трійками чисел X_i, Y_i, L_i, де X_i - стартове місто дороги, Y_i - кінцевий, а L_i - її довжина (1 ≤ X_i, Y_i ≤ N, X_i ≠ Y_i, 1 ≤ L_i ≤ 1000). Між кожною парою міст існує не більше однієї дороги у кожному напрямку.
Сума значень N по усім наборів вхідних даних не перевищує 300.
Вихідні дані
Для кожного набору вхідних даних виведіть шуканий найменший бюджет.