Problem description

Jasio został burmistrzem Krasnalandu – krainy składającej się z N wysp zamieszkanych przez krasnale. Wyspy są ponumerowane od 1 do N. Początkowo na żadnej wyspie nie ma ani lotniska, ani portu i żadnych dwóch wysp nie łączy droga. Jako nowy burmistrz Jasio chce nareszcie skomunikować cały Krasnaland ze sobą.

By osiągnąć ten cel, Jasio może:

• Wybrać liczbę i (1 ≤ i ≤ N) i wybudować na wyspie i lotnisko za X_i krasnalarów.
• Wybrać liczbę i (1 ≤ i ≤ N) i wybudować na wyspie i port za Y_i krasnalarów.
• Wybrać liczbę i (1 ≤ i ≤ M) i wybudować dwukierunkową drogę łączącą wyspy A_i i B_i za Z_i krasnalarów.

Jasio chce, żeby dla każdej pary różnych wysp U i V dało się dostać z wyspy U na wyspę V, wykonując następujące operacje dowolną liczbę razy w dowolnej kolejności:

• Jeśli na wyspach S i T znajdują się lotniska – przelecieć z wyspy S na wyspę T.
• Jeśli na wyspach S i T znajdują się porty – przepłynąć z wyspy S na wyspę T.
• Jeśli wyspy S i T są połączone drogą – przejechać z wyspy S na wyspę T.

Budżet Krasnalandu jest ograniczony, więc Jasio poprosił Cię o napisanie programu, który wyznaczy minimalny koszt (w krasnalarach) skomunikowania całej krainy.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite N i M – liczba wysp w Krasnalandzie i liczba możliwych do wybudowania dróg.

W drugim wierszu wejścia znajduje się ciąg N liczb całkowitych X₁, X₂, …, X_N – ceny budowy lotniska na odpowiednich wyspach w krasnalarach.

W trzecim wierszu wejścia znajduje się ciąg N liczb całkowitych Y₁, Y₂, …, Y_N – ceny budowy portu na odpowiednich wyspach w krasnalarach.

W każdym z kolejnych M wierszy znajdują się trzy liczby całkowite A_i, B_i, Z_i – wyspy, które może połączyć droga, oraz jej cena.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita – minimalny koszt skomunikowania Krasnalandu w krasnalarach.

Ograniczenia

2 ≤ N ≤ 200 000, 1 ≤ M ≤ 200 000, 1 ≤ X_i, Y_i, Z_i ≤ 10⁹, 1 ≤ A_i < B_i ≤ N, (A_i,B_i) ≠ (A_j,B_j) dla i ≠ j.

Przykłady

4 2
1 20 4 7
20 2 20 3
1 3 5
1 4 6

16

3 1
1 1 1
10 10 10
1 2 100

3

7 8
35 29 36 88 58 15 25
99 7 49 61 67 4 57
2 3 3
2 5 36
2 6 89
1 6 24
5 7 55
1 3 71
3 4 94
5 6 21

160