Перевіряючи стан електростанцій та ліній електропередач (ЛЕП) між містами король Укрії зауважив що вони в жахливому стані і місцями несправні, тому він хоче створити нову мережу електропостачання. Але він хоче це зробити витративши мінімальну кількість коштів. Тому він доручив вам це завдання.

Відомо що В Укрії є n міст, але ЛЕП можна прокласти лише між m парами міст, причому вартість проведення ЛЕП між містом ~v_i~ та ~u_i~ становить ~a_i~ ~(0 \le i <m)~. Також в кожному місті можна побудувати електростанцію, яка забезпечить електроенергією це місто, а також всі з'єднані з ним, а також всі з'єднані з ними і тд. В місті ~i~ вартість побудови електростанції становить ~b_i~ ~(0 \le i <m)~.</p>

Можна показати що при заданих обмеженнях це завжди можливо.

Input

В першому рядку задано 2 цілі числа ~n,m~ ~(0 < n , m \le 10^5).~

В наступних m рядках вводяться 3 цілі числа ~v_i~ , ~u_i~ , ~a_i~ ~(0 < v_i,u_i \le n~, ~v_i~ ~!=~ ~u_i~, ~0<a_i \le 10^9).~</p>

В наступному рядку вводиться n цілих чисел ~b_i~ ~(0 < i \le n~, ~0<b_i \le 10^9).~</p>

Output

Найменшу кількість коштів щоб забезпечити енергією всі міста.

Sample Input 1

8 7
1 2 5
1 4 6
2 3 7
2 4 9
4 5 10
6 7 4
6 8 5
13 12 14 11 5 2 1 3

Sample Output 1

39