{"problem":{"name":"Transportation","description":{"content":"The Republic of AtCoder has $N$ islands. Initially, none of the islands has an airport or harbor, and there is no road between any two of them. Takahashi, the king, will provide some means of transpor","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc270_f"},"statements":[{"statement_type":"Markdown","content":"The Republic of AtCoder has $N$ islands. Initially, none of the islands has an airport or harbor, and there is no road between any two of them. Takahashi, the king, will provide some means of transportation between these islands. Specifically, he can do the following operations any number of times in any order.\n\n*   Choose an integer $i$ such that $1\\leq i\\leq N$ and pay a cost of $X_i$ to build an airport on island $i$.\n*   Choose an integer $i$ such that $1\\leq i\\leq N$ and pay a cost of $Y_i$ to build a harbor on island $i$.\n*   Choose an integer $i$ such that $1\\leq i\\leq M$ and pay a cost of $Z_i$ to build a road that bidirectionally connects island $A_i$ and island $B_i$.\n\nTakahashi's objective is to make it possible, for every pair of different islands $U$ and $V$, to reach island $V$ from island $U$ when one can perform the following actions any number of times in any order.\n\n*   When islands $S$ and $T$ both have airports, go from island $S$ to island $T$.\n*   When islands $S$ and $T$ both have harbors, go from island $S$ to island $T$.\n*   When islands $S$ and $T$ are connected by a road, go from island $S$ to island $T$.\n\nFind the minimum total cost Takahashi needs to pay to achieve his objective.\n\n## Constraints\n\n*   $2 \\leq N \\leq 2\\times 10^5$\n*   $1 \\leq M \\leq 2\\times 10^5$\n*   $1\\leq X_i\\leq 10^9$\n*   $1\\leq Y_i\\leq 10^9$\n*   $1\\leq A_i<B_i\\leq N$\n*   $1\\leq Z_i\\leq 10^9$\n*   $(A_i,B_i)\\neq (A_j,B_j)$, if $i\\neq j$.\n*   All values in the input are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$\n$X_1$ $X_2$ $\\ldots$ $X_N$\n$Y_1$ $Y_2$ $\\ldots$ $Y_N$\n$A_1$ $B_1$ $Z_1$\n$A_2$ $B_2$ $Z_2$\n$\\vdots$\n$A_M$ $B_M$ $Z_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc270_f","tags":[],"sample_group":[["4 2\n1 20 4 7\n20 2 20 3\n1 3 5\n1 4 6","16\n\nTakahashi will build the following infrastructure.\n\n*   Pay a cost of $X_1=1$ to build an airport on island $1$.\n*   Pay a cost of $X_3=4$ to build an airport on island $3$.\n*   Pay a cost of $Y_2=2$ to build a harbor on island $2$.\n*   Pay a cost of $Y_4=3$ to build a harbor on island $4$.\n*   Pay a cost of $Z_2=6$ to build a road connecting island $1$ and island $4$.\n\nThen, the objective will be achieved at a cost of $16$. There is no way to achieve the objective for a cost of $15$ or less, so $16$ should be printed."],["3 1\n1 1 1\n10 10 10\n1 2 100","3\n\nIt is not mandatory to build all three types of facilities at least once."],["7 8\n35 29 36 88 58 15 25\n99 7 49 61 67 4 57\n2 3 3\n2 5 36\n2 6 89\n1 6 24\n5 7 55\n1 3 71\n3 4 94\n5 6 21","160"]],"created_at":"2026-03-03 11:01:13"}}