{"problem":{"name":"Forest","description":{"content":"You are given a forest with $N$ vertices and $M$ edges. The vertices are numbered $0$ through $N-1$. The edges are given in the format $(x_i,y_i)$, which means that Vertex $x_i$ and $y_i$ are connecte","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"apc001_d"},"statements":[{"statement_type":"Markdown","content":"You are given a forest with $N$ vertices and $M$ edges. The vertices are numbered $0$ through $N-1$. The edges are given in the format $(x_i,y_i)$, which means that Vertex $x_i$ and $y_i$ are connected by an edge.\nEach vertex $i$ has a value $a_i$. You want to add edges in the given forest so that the forest becomes connected. To add an edge, you choose two different vertices $i$ and $j$, then span an edge between $i$ and $j$. This operation costs $a_i + a_j$ dollars, and afterward neither Vertex $i$ nor $j$ can be selected again.\nFind the minimum total cost required to make the forest connected, or print `Impossible` if it is impossible.\n\n## Constraints\n\n*   $1 ≤ N ≤ 100,000$\n*   $0 ≤ M ≤ N-1$\n*   $1 ≤ a_i ≤ 10^9$\n*   $0 ≤ x_i,y_i ≤ N-1$\n*   The given graph is a forest.\n*   All input values are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$a_0$ $a_1$ $..$ $a_{N-1}$\n$x_1$ $y_1$\n$x_2$ $y_2$\n$:$\n$x_M$ $y_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"apc001_d","tags":[],"sample_group":[["7 5\n1 2 3 4 5 6 7\n3 0\n4 0\n1 2\n1 3\n5 6","7\n\nIf we connect vertices $0$ and $5$, the graph becomes connected, for the cost of $1 + 6 = 7$ dollars."],["5 0\n3 1 4 1 5","Impossible\n\nWe can't make the graph connected."],["1 0\n5","0\n\nThe graph is already connected, so we do not need to add any edges."]],"created_at":"2026-03-03 11:01:14"}}