stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (n); i++)

#define all(x) (x).begin(), (x).end()

#define rall(x) (x).rbegin(), (x).rend()

using ll = long long;

using namespace std;



struct P {

    ll taste;

    int a;

    int b;

    int c;



    bool operator<(const P &d) const {

        if (a == d.a && b == d.b && c == d.c) {

            return taste < d.taste;

        } else if (a != d.a) {

            return a < d.a;

        } else if (b != d.b) {

            return b < d.b;

        } else {

            return c < d.c;

        }

    };

};



int main() {

    int X, Y, Z, K;

    cin >> X >> Y >> Z >> K;

    vector<ll> A(X + 2000, -10000000000);

    vector<ll> B(Y + 2000, -10000000000);

    vector<ll> C(Z + 2000, -10000000000);

    rep(i, X) cin >> A[i];

    rep(i, Y) cin >> B[i];

    rep(i, Z) cin >> C[i];

    sort(rall(A));

    sort(rall(B));

    sort(rall(C));



    auto compare = [](P a, P b) {

      return a.taste < b.taste;

    };



    priority_queue<P,vector<P>,decltype(compare)> pq {compare};

    P init = {A[0] + B[0] + C[0], 0, 0, 0};

    pq.push(init);

    map<P, int> cnt;

    cnt[init]++;

    vector<ll> ans;



    while (!pq.empty() && ans.size() < K) {

        P q = pq.top();

        pq.pop();

        ans.push_back(q.taste);

        P newq1 = {A[q.a + 1] + B[q.b] + C[q.c], q.a + 1, q.b, q.c};

        P newq2 = {A[q.a] + B[q.b + 1] + C[q.c], q.a, q.b + 1, q.c};

        P newq3 = {A[q.a] + B[q.b] + C[q.c + 1], q.a, q.b, q.c + 1};



        if (cnt[newq1] == 0) {

            pq.push(newq1);

            cnt[newq1]++;

        }

        if (cnt[newq2] == 0) {

            pq.push(newq2);

            cnt[newq2]++;

        }

        if (cnt[newq3] == 0) {

            pq.push(newq3);

            cnt[newq3]++;

        }

    }

    rep(i, K) cout << ans[i] << endl;

}


// Faster C++ solution for the same problem (measured speedup: 1.108367926339862x):
#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (n); i++)

#define all(x) (x).begin(), (x).end()

#define rall(x) (x).rbegin(), (x).rend()

using ll = long long;

using namespace std;



vector<ll> ans;



int main() {

    int X, Y, Z, K;

    cin >> X >> Y >> Z >> K;

    vector<ll> A(X);

    vector<ll> B(Y);

    vector<ll> C(Z);

    rep(i, X) cin >> A[i];

    rep(i, Y) cin >> B[i];

    rep(i, Z) cin >> C[i];

    sort(rall(A));

    sort(rall(B));

    sort(rall(C));



    rep(i,X)rep(j,Y)rep(k,Z){

        if(i*j*k>K)break;

        ans.push_back(A[i]+B[j]+C[k]);

    }

    sort(rall(ans));

 

    rep(i, K) cout << ans[i] << endl;

}
// Slower C++ solution:
#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <vector>

using namespace std;

const int MAXN = 100000;



int n, m;

int fa[MAXN+5];

int val[MAXN+5];

vector <int> blk[MAXN+5];

vector <int> ansEdge;

long long int ans;



int SetFind(int x)

{

    if(fa[x] != x)

        return fa[x] = SetFind(fa[x]);

    return fa[x];

}



void SetInit(int n)

{

    for(int i = 1; i <= n; i++)

        fa[i] = i;

}



int main()

{

    int blkcnt;



    cin >> n >> m ;

    SetInit(n);

    blkcnt = n;



    for(int i = 1; i <= n; i++)

        cin >> val[i] ;

        //blk[i].push_back(val[i]);





    for(int i = 1; i <= m; i++)

    {

        int u, v;

        cin >> u >> v;

        u++, v++;

        if(SetFind(u) != SetFind(v))

            fa[SetFind(u)] = SetFind(v), blkcnt--;

    }



    for(int i = 1; i <= n; i++)

        blk[SetFind(i)].push_back(val[i]);

/*

    for(int i = 1; i <= n; i++)

    {

        if(!blk[i].empty())

            cout << blk[i].size() << endl ;

    }

*/

    if(blkcnt <= 1)

    {

        cout << 0 << endl ;

        return 0;

    }



    blkcnt -= 2;



    for(int i = 1; i <= n; i++)

        if(!blk[i].empty())

        {

            sort(blk[i].begin(), blk[i].end());

            ans += blk[i][0];

            for(int k = 1; k < blk[i].size(); k++)

                ansEdge.push_back(blk[i][k]);

        }



    if(ansEdge.size() < blkcnt)

    {

        cout << "Impossible" << endl;

        return 0;

    }



    sort(ansEdge.begin(), ansEdge.end());



    for(int i = 0; i < blkcnt; i++)

        ans += ansEdge[i] ;



    cout << ans << endl ;

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 10.515504466064298x):
#include <stdio.h>

#include <string.h>

#include <algorithm>

#define N 100010

int n,m,c[N],d[N],k[N];char vis[N];

int fa[N];

int find(int x) {

	return ~fa[x]?fa[x]=find(fa[x]):x;

}

inline void join(int a,int b) {

	int x=find(a),y=find(b);

	if(x!=y) {

		fa[x]=y;

		if(d[k[y]]>d[k[x]]) k[y]=k[x];

	}

}

int main() {

	int a,b;long long ans=0;

	scanf("%d%d",&n,&m);

	if(n-2*m>2) {

		puts("Impossible");

		return 0;

	}

	if(n-1==m) {

		puts("0");

		return 0;

	}

	memset(fa,-1,sizeof(fa));

	for(int i=0;i<n;++i) scanf("%d",d+i),k[i]=i;

	for(int i=0;i<m;++i) {

		scanf("%d%d",&a,&b);

		join(a,b);

	}

	for(int i=0;i<n;++i) if(!~fa[i]) vis[k[i]]=1,ans+=d[k[i]];

	a=0;

	for(int i=0;i<n;++i) if(!vis[i]) c[a++]=d[i];

	std::sort(c,c+a);

	b=n-m-2;

	for(int i=0;i<b;++i) ans+=c[i];

	printf("%lld",ans);

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;



const int N = 100010;



struct Heap{

	Heap *l, *r;

	int val, len, size;

}*root[N], Pool[N * 2], *cur = Pool;



int fa[N];

priority_queue<pair<int, int> >Q;



Heap *newnode(int val_)

{

	cur++;

	cur -> len = 0;

	cur -> size = 1;

	cur -> val = val_;

	cur -> l = cur -> r = NULL;

	return cur;

}



Heap *Merge(Heap *A, Heap *B)

{

	if(!A)return B;

	if(!B)return A;

	if(A -> val > B -> val)swap(A, B);

	A -> r = Merge(A -> r, B);

	A -> size = (A -> l ? A -> l -> size : 0) + (A -> r ? A -> r -> size : 0) + 1;

	if(!(A -> l))swap(A -> l, A -> r);

	if(A -> l && A -> r && A -> l -> len < A -> r -> len)swap(A -> l, A -> r);

	if(A -> r)A -> len = A -> r -> len + 1;

	else A -> len = 0;

	return A;

}



int getf(int u)

{

	if(u == fa[u])return u;

	return fa[u] = getf(fa[u]);

}



int main()

{

	int n, m;

	scanf("%d%d", &n, &m);

	for(int i = 1; i <= n; i++)

	{

		int val;

		scanf("%d", &val);

		root[i] = newnode(val);

		fa[i] = i;

	}

	for(int i = 1; i <= m; i++)

	{

		int x, y;

		scanf("%d%d", &x, &y);

		x++; y++;

		int u, v;

		u = getf(x), v = getf(y);

		if(u > v)swap(u, v);

		fa[v] = u;

		root[u] = Merge(root[u], root[v]);

	}

	for(int i = 1; i <= n; i++)

		if(getf(i) == i)

		{

			Q.push(make_pair(root[i] -> size, i));

		}

	long long ans = 0;

	while(Q.size() > 1)

	{

		pair<int, int> v1 = Q.top();

		Q.pop();

		pair<int, int> v2 = Q.top();

		Q.pop();

		int u = v1.second, v = v2.second;

		if(!root[u] || !root[v])

		{

			puts("Impossible");

			return 0;

		}

		ans += (root[u] -> val + root[v] -> val);

		if(u > v)swap(u, v);

		fa[v] = u;

		root[u] = Merge(Merge(root[u] -> l, root[u] -> r), Merge(root[v] -> l, root[v] -> r));

		if(root[u])Q.push(make_pair(root[u] -> size, u));

		else Q.push(make_pair(0, u));

	}

	cout << ans << endl;

}

// Faster C++ solution for the same problem (measured speedup: 2.973226169566292x):
#include <stdio.h>

#include <string.h>

#include <algorithm>

#define N 100010

int n,m,c[N],d[N],k[N];char vis[N];

int fa[N];

int find(int x) {

	return ~fa[x]?fa[x]=find(fa[x]):x;

}

inline void join(int a,int b) {

	int x=find(a),y=find(b);

	if(x!=y) {

		fa[x]=y;

		if(d[k[y]]>d[k[x]]) k[y]=k[x];

	}

}

int main() {

	int a,b;long long ans=0;

	scanf("%d%d",&n,&m);

	if(n-2*m>2) {

		puts("Impossible");

		return 0;

	}

	if(n-1==m) {

		puts("0");

		return 0;

	}

	memset(fa,-1,sizeof(fa));

	for(int i=0;i<n;++i) scanf("%d",d+i),k[i]=i;

	for(int i=0;i<m;++i) {

		scanf("%d%d",&a,&b);

		join(a,b);

	}

	for(int i=0;i<n;++i) if(!~fa[i]) vis[k[i]]=1,ans+=d[k[i]];

	a=0;

	for(int i=0;i<n;++i) if(!vis[i]) c[a++]=d[i];

	std::sort(c,c+a);

	b=n-m-2;

	for(int i=0;i<b;++i) ans+=c[i];

	printf("%lld",ans);

	return 0;

}
// Slower C++ solution:
#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <vector>

using namespace std;

const int MAXN = 100000;



int n, m;

int fa[MAXN+5];

int val[MAXN+5];

vector <int> blk[MAXN+5];

vector <int> ansEdge;

long long int ans;



int SetFind(int x)

{

    if(fa[x] != x)

        return fa[x] = SetFind(fa[x]);

    return fa[x];

}



void SetInit(int n)

{

    for(int i = 1; i <= n; i++)

        fa[i] = i;

}



int main()

{

    int blkcnt;



    cin >> n >> m ;

    SetInit(n);

    blkcnt = n;



    for(int i = 1; i <= n; i++)

        cin >> val[i] ;

        //blk[i].push_back(val[i]);





    for(int i = 1; i <= m; i++)

    {

        int u, v;

        cin >> u >> v;

        u++, v++;

        if(SetFind(u) != SetFind(v))

            fa[SetFind(u)] = SetFind(v), blkcnt--;

    }



    for(int i = 1; i <= n; i++)

        blk[SetFind(i)].push_back(val[i]);

/*

    for(int i = 1; i <= n; i++)

    {

        if(!blk[i].empty())

            cout << blk[i].size() << endl ;

    }

*/

    if(blkcnt <= 1)

    {

        cout << 0 << endl ;

        return 0;

    }



    blkcnt -= 2;



    for(int i = 1; i <= n; i++)

        if(!blk[i].empty())

        {

            sort(blk[i].begin(), blk[i].end());

            ans += blk[i][0];

            for(int k = 1; k < blk[i].size(); k++)

                ansEdge.push_back(blk[i][k]);

        }



    if(ansEdge.size() < blkcnt)

    {

        cout << "Impossible" << endl;

        return 0;

    }



    sort(ansEdge.begin(), ansEdge.end());



    for(int i = 0; i < blkcnt; i++)

        ans += ansEdge[i] ;



    cout << ans << endl ;

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 2.527625553909054x):
#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <algorithm>

#define MN 200000

#define MM 200000

#define INF 0x7fffffff

int n,m,a[MN+5];

int hd[MN+5],nxt[MM+5],to[MM+5],rn=0;

int mi1,mi2,lc=0,l[MN+5],lft=2,cnt=0;

long long ans=0;

bool usd[MN+5],usd2[MN+5];

inline void add(int u,int v){

	++rn;

	nxt[rn]=hd[u],hd[u]=rn;

	to[rn]=v;

}

void dfs(int u){

	usd[u]=true;

	if(a[u]<mi1){

		mi1=a[u];

		mi2=u;

	}

	for(int i=hd[u];i!=-1;i=nxt[i])

		if(!usd[to[i]]) dfs(to[i]);

}

int main(){

	memset(hd,0xff,sizeof(hd));

	memset(usd,0,sizeof(usd));

	memset(usd2,0,sizeof(usd2));

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++)

		scanf("%d",&a[i]);

	for(int i=1;i<=m;i++){

		int u,v; scanf("%d%d",&u,&v);

		u++,v++; add(u,v),add(v,u);

	}

	for(int i=1;i<=n;i++){

		mi1=INF;

		if(!usd[i]) dfs(i);

		else continue;

		cnt++;

		ans+=mi1; usd2[mi2]=true;

	}

	if(cnt==1) puts("0"),exit(0);

	for(int i=1;i<=n;i++)

		if(!usd2[i]) l[++lc]=a[i];

	if(lc<(n-1-m)*2-cnt) puts("Impossible"),exit(0);

	std::sort(l+1,l+1+lc);

	for(int i=1;i<=(n-1-m)*2-cnt;i++)

		ans+=l[i];

	printf("%lld",ans);

}
// Slower C++ solution:
#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <algorithm>

#define MN 200000

#define MM 200000

#define INF 0x7fffffff

int n,m,a[MN+5];

int hd[MN+5],nxt[MM+5],to[MM+5],rn=0;

int mi1,mi2,lc=0,l[MN+5],lft=2,cnt=0;

long long ans=0;

bool usd[MN+5],usd2[MN+5];

inline void add(int u,int v){

	++rn;

	nxt[rn]=hd[u],hd[u]=rn;

	to[rn]=v;

}

void dfs(int u){

	usd[u]=true;

	if(a[u]<mi1){

		mi1=a[u];

		mi2=u;

	}

	for(int i=hd[u];i!=-1;i=nxt[i])

		if(!usd[to[i]]) dfs(to[i]);

}

int main(){

	memset(hd,0xff,sizeof(hd));

	memset(usd,0,sizeof(usd));

	memset(usd2,0,sizeof(usd2));

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++)

		scanf("%d",&a[i]);

	for(int i=1;i<=m;i++){

		int u,v; scanf("%d%d",&u,&v);

		u++,v++; add(u,v),add(v,u);

	}

	for(int i=1;i<=n;i++){

		mi1=INF;

		if(!usd[i]) dfs(i);

		else continue;

		cnt++;

		ans+=mi1; usd2[mi2]=true;

	}

	if(cnt==1) puts("0"),exit(0);

	for(int i=1;i<=n;i++)

		if(!usd2[i]) l[++lc]=a[i];

	if(lc<(n-1-m)*2-cnt) puts("Impossible"),exit(0);

	std::sort(l+1,l+1+lc);

	for(int i=1;i<=(n-1-m)*2-cnt;i++)

		ans+=l[i];

	printf("%lld",ans);

}

// Faster C++ solution for the same problem (measured speedup: 1.403074276336085x):
#include <bits/stdc++.h>





using namespace std;

typedef long long LL;

const int maxn = 100005;

int a[maxn], fa[maxn], mi[maxn], id[maxn], vis[maxn];

int n, m;



void Init()

{

    for(int i = 0; i <= n; i++)

    {

        fa[i] = i;

        mi[i] = a[i];

        id[i] = i;

    }

}



int Find(int x)

{

    return fa[x] == x ? x : fa[x] = Find(fa[x]);

}



void Merge(int x, int y)

{

    int fx = Find(x), fy = Find(y);

    fa[fx] = fy;

    if(mi[fy] > mi[fx])

    {

        mi[fy] = mi[fx];

        id[fy] = id[fx];

    }

}



int main()

{

    scanf("%d%d", &n, &m);

    multiset<int> s;

    for(int i = 1; i <= n; i++)

    {

        scanf("%d", &a[i]);

        s.insert(a[i]);

    }

    Init();

    for(int i = 1; i <= m; i++)

    {

        int u, v;

        scanf("%d%d", &u, &v);

        Merge(u + 1, v + 1);

    }

    int num = 0;

    LL ans = 0;

    for(int i = 1; i <= n; i++)

    {

        if(Find(i) == i)

        {

            num++;

            ans += mi[fa[i]];

            s.erase(s.find(mi[fa[i]]));

        }

    }

    if(n < 2 * num - 2)

        printf("Impossible\n");

    else if(num == 1)

        printf("0\n");

    else

    {

        int cnt = 0;

        multiset<int>::iterator it;

        for(it = s.begin(); it != s.end() && cnt < num - 2; it++)

        {

            cnt++;

            ans += *it;

        }

        printf("%lld\n", ans);

    }

    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

inline int read(){

	int x=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

	return x*f;

}

#define MN 100005

int n,m,fa[MN],vis[MN],cnt,p[MN],ct;

long long a[MN],ans;

int findf(int x){return fa[x]==x?fa[x]:fa[x]=findf(fa[x]);}

void union_(int x,int y){x=findf(x);y=findf(y);fa[x]=y;return;}

vector<int> pic[MN];

int main(){

	n=read(),m=read();

	register int i,j,x,y;

	for(i=1;i<=n;i++) a[i]=read(),fa[i]=i;

	for(i=1;i<=m;i++){

		x=read()+1,y=read()+1;

		union_(x,y);

	}

	if(m==n-1) return puts("0"),0;

	if((n-m-1)*2>n) return puts("Impossible\n"),0;

	for(i=1;i<=n;i++){

		if(vis[findf(i)]) pic[vis[fa[i]]].push_back(a[i]);

		else pic[vis[findf(i)]=++cnt].push_back(a[i]);

	}

	for(i=1;i<=cnt;i++){

		sort(pic[i].begin(),pic[i].end()),ans+=pic[i][0];

		for(j=1;j<pic[i].size();j++) p[++ct]=pic[i][j];

	}

	sort(p+1,p+ct+1);

	for(i=1;i<=n-m-2;i++) ans+=p[i];

	printf("%lld",ans);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.5226865280713584x):
#include <bits/stdc++.h>





using namespace std;

typedef long long LL;

const int maxn = 100005;

int a[maxn], fa[maxn], mi[maxn], id[maxn], vis[maxn];

int n, m;



void Init()

{

    for(int i = 0; i <= n; i++)

    {

        fa[i] = i;

        mi[i] = a[i];

        id[i] = i;

    }

}



int Find(int x)

{

    return fa[x] == x ? x : fa[x] = Find(fa[x]);

}



void Merge(int x, int y)

{

    int fx = Find(x), fy = Find(y);

    fa[fx] = fy;

    if(mi[fy] > mi[fx])

    {

        mi[fy] = mi[fx];

        id[fy] = id[fx];

    }

}



int main()

{

    scanf("%d%d", &n, &m);

    multiset<int> s;

    for(int i = 1; i <= n; i++)

    {

        scanf("%d", &a[i]);

        s.insert(a[i]);

    }

    Init();

    for(int i = 1; i <= m; i++)

    {

        int u, v;

        scanf("%d%d", &u, &v);

        Merge(u + 1, v + 1);

    }

    int num = 0;

    LL ans = 0;

    for(int i = 1; i <= n; i++)

    {

        if(Find(i) == i)

        {

            num++;

            ans += mi[fa[i]];

            s.erase(s.find(mi[fa[i]]));

        }

    }

    if(n < 2 * num - 2)

        printf("Impossible\n");

    else if(num == 1)

        printf("0\n");

    else

    {

        int cnt = 0;

        multiset<int>::iterator it;

        for(it = s.begin(); it != s.end() && cnt < num - 2; it++)

        {

            cnt++;

            ans += *it;

        }

        printf("%lld\n", ans);

    }

    return 0;

}
// Slower C++ solution:
#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <algorithm>

#define MN 200000

#define MM 200000

#define INF 0x7fffffff

int n,m,a[MN+5];

int hd[MN+5],nxt[MM+5],to[MM+5],rn=0;

int mi1,mi2,lc=0,l[MN+5],lft=2,cnt=0;

long long ans=0;

bool usd[MN+5],usd2[MN+5];

inline void add(int u,int v){

	++rn;

	nxt[rn]=hd[u],hd[u]=rn;

	to[rn]=v;

}

void dfs(int u){

	usd[u]=true;

	if(a[u]<mi1){

		mi1=a[u];

		mi2=u;

	}

	for(int i=hd[u];i!=-1;i=nxt[i])

		if(!usd[to[i]]) dfs(to[i]);

}

int main(){

	memset(hd,0xff,sizeof(hd));

	memset(usd,0,sizeof(usd));

	memset(usd2,0,sizeof(usd2));

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++)

		scanf("%d",&a[i]);

	for(int i=1;i<=m;i++){

		int u,v; scanf("%d%d",&u,&v);

		u++,v++; add(u,v),add(v,u);

	}

	for(int i=1;i<=n;i++){

		mi1=INF;

		if(!usd[i]) dfs(i);

		else continue;

		cnt++;

		ans+=mi1; usd2[mi2]=true;

	}

	if(cnt==1) puts("0"),exit(0);

	for(int i=1;i<=n;i++)

		if(!usd2[i]) l[++lc]=a[i];

	if(lc<(n-1-m)*2-cnt) puts("Impossible"),exit(0);

	std::sort(l+1,l+1+lc);

	for(int i=1;i<=(n-1-m)*2-cnt;i++)

		ans+=l[i];

	printf("%lld",ans);

}

// Faster C++ solution for the same problem (measured speedup: 1.4030666281606783x):
#include <bits/stdc++.h>





using namespace std;

typedef long long LL;

const int maxn = 100010;

int a[maxn], fa[maxn], mi[maxn], id[maxn], vis[maxn];

int n, m;



void Init()

{

    for(int i = 0; i <= n; i++)

    {

        fa[i] = i;

        mi[i] = a[i];

        id[i] = i;

    }

}



int Find(int x)

{

    return fa[x] == x ? x : fa[x] = Find(fa[x]);

}



void Merge(int x, int y)

{

    int fx = Find(x), fy = Find(y);

    fa[fx] = fy;

    if(mi[fy] > mi[fx])

    {

        mi[fy] = mi[fx];

        id[fy] = id[fx];

    }

}



int main()

{

    scanf("%d%d", &n, &m);

    multiset<int> s;

    for(int i = 1; i <= n; i++)

    {

        scanf("%d", &a[i]);

        s.insert(a[i]);

    }

    Init();

    for(int i = 1; i <= m; i++)

    {

        int u, v;

        scanf("%d%d", &u, &v);

        Merge(u + 1, v + 1);

    }

    int num = 0;

    LL ans = 0;

    for(int i = 1; i <= n; i++)

    {

        if(Find(i) == i)

        {

            num++;

            ans += mi[fa[i]];

            s.erase(s.find(mi[fa[i]]));

        }

    }

    if(n < 2 * num - 2)

        printf("Impossible\n");

    else if(num == 1)

        printf("0\n");

    else

    {

        int cnt = 0;

        multiset<int>::iterator it;

        for(it = s.begin(); it != s.end() && cnt < num - 2; it++)

        {

            cnt++;

            ans += *it;

        }

        printf("%lld\n", ans);

    }

    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

inline int read(){

	int x=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

	return x*f;

}

#define MN 100005

int n,m,fa[MN],vis[MN],cnt,p[MN],ct;

long long a[MN],ans;

int findf(int x){return fa[x]==x?fa[x]:fa[x]=findf(fa[x]);}

void union_(int x,int y){x=findf(x);y=findf(y);fa[x]=y;return;}

vector<int> pic[MN];

int main(){

	n=read(),m=read();

	register int i,j,x,y;

	for(i=1;i<=n;i++) a[i]=read(),fa[i]=i;

	for(i=1;i<=m;i++){

		x=read()+1,y=read()+1;

		union_(x,y);

	}

	if(m==n-1) return puts("0"),0;

	if((n-m-1)*2>n) return puts("Impossible\n"),0;

	for(i=1;i<=n;i++){

		if(vis[findf(i)]) pic[vis[fa[i]]].push_back(a[i]);

		else pic[vis[findf(i)]=++cnt].push_back(a[i]);

	}

	for(i=1;i<=cnt;i++){

		sort(pic[i].begin(),pic[i].end()),ans+=pic[i][0];

		for(j=1;j<pic[i].size();j++) p[++ct]=pic[i][j];

	}

	sort(p+1,p+ct+1);

	for(i=1;i<=n-m-2;i++) ans+=p[i];

	printf("%lld",ans);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.52266732586309x):
#include <bits/stdc++.h>





using namespace std;

typedef long long LL;

const int maxn = 100010;

int a[maxn], fa[maxn], mi[maxn], id[maxn], vis[maxn];

int n, m;



void Init()

{

    for(int i = 0; i <= n; i++)

    {

        fa[i] = i;

        mi[i] = a[i];

        id[i] = i;

    }

}



int Find(int x)

{

    return fa[x] == x ? x : fa[x] = Find(fa[x]);

}



void Merge(int x, int y)

{

    int fx = Find(x), fy = Find(y);

    fa[fx] = fy;

    if(mi[fy] > mi[fx])

    {

        mi[fy] = mi[fx];

        id[fy] = id[fx];

    }

}



int main()

{

    scanf("%d%d", &n, &m);

    multiset<int> s;

    for(int i = 1; i <= n; i++)

    {

        scanf("%d", &a[i]);

        s.insert(a[i]);

    }

    Init();

    for(int i = 1; i <= m; i++)

    {

        int u, v;

        scanf("%d%d", &u, &v);

        Merge(u + 1, v + 1);

    }

    int num = 0;

    LL ans = 0;

    for(int i = 1; i <= n; i++)

    {

        if(Find(i) == i)

        {

            num++;

            ans += mi[fa[i]];

            s.erase(s.find(mi[fa[i]]));

        }

    }

    if(n < 2 * num - 2)

        printf("Impossible\n");

    else if(num == 1)

        printf("0\n");

    else

    {

        int cnt = 0;

        multiset<int>::iterator it;

        for(it = s.begin(); it != s.end() && cnt < num - 2; it++)

        {

            cnt++;

            ans += *it;

        }

        printf("%lld\n", ans);

    }

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



typedef long long ll;



const int maxn = 1e5 + 5;



int n, m, k;

int w[maxn], f[maxn];

ll ans;

priority_queue <int, vector<int>, greater<int>> q[maxn];

multiset <int> s;



int find(int x)

{

	return f[x] == x ? x : f[x] = find(f[x]);

}



void merge(int x, int y)

{

	int fx = find(x);

	int fy = find(y);

	if(fx != fy)

		f[fx] = fy;

}



int main()

{

	int u, v;

	scanf("%d%d", &n, &m);

	k = n - m;

	if(2 * k - 2 > n)

	{

		puts("Impossible");

		return 0;

	}

	if(k == 1)

	{

		puts("0");

		return 0;

	}

	for(int i = 1; i <= n; i++)

	{

		scanf("%d", &w[i]);

		f[i] = i;

	}

	for(int i = 1; i <= m; i++)

	{

		scanf("%d%d", &u, &v);

		u++, v++;

		merge(u, v);

	}

	for(int i = 1; i <= n; i++)

	{

		find(i);

		q[f[i]].push(w[i]);

	}

	for(int i = 1; i <= n; i++)

		if(!q[i].empty())

		{

			ans += q[i].top();

			q[i].pop();

	//		printf("val = %lld\n", val);

		}

	for(int i = 1; i <= n; i++)

		while(!q[i].empty())

		{

			s.insert(q[i].top());

			q[i].pop();

		}	

//	for(auto it = s.begin(); it != s.end(); it++)

//		printf("%d\n", *it);

	auto it = s.begin();

	for(int i = 1; i <= k - 2; i++, it++)

	{

		ans += *it;

	//	printf("%lld\n", ans);

	}

	printf("%lld\n", ans);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 22.69959233325461x):
#include<cstdio>

#include<cstring>

#include<algorithm>

#define maxn 100005

#define LL long long

using namespace std;

int n,m,fa[maxn],use[maxn],cnt;

LL ans;

struct node { int w;bool vis; } a[maxn];

bool cmp(node p,node q) 

{

	if(p.vis) return false;

	if(q.vis) return true;

	return p.w<q.w; 

}

int find(int x)

{

	if(fa[x]==x) return x;

	return fa[x]=find(fa[x]);

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++)

	{

		scanf("%d",&a[i].w);

		fa[i]=i;use[i]=i;

		a[i].vis=true;

	}

	for(int i=1;i<=m;i++)

	{

		int u,v;

		scanf("%d%d",&u,&v);

		u++,v++;

		int r1=find(u),r2=find(v);

		if(r1!=r2)

		{

			if(a[use[r2]].w<a[use[r1]].w)

			{

				a[use[r1]].vis=false;

				use[r1]=use[r2];

			}

			else a[use[r2]].vis=false;

			fa[r2]=r1;

		}

	}

	for(int i=1;i<=n;i++)

		if(find(i)==i) 

		{

			ans+=1ll*a[use[i]].w;

			cnt++;

		}

	if(cnt==1)

	{

		printf("0\n");

		return 0;

	}

	sort(a+1,a+n+1,cmp);

	for(int i=1;i<=cnt-2;i++)

		if(a[i].vis)

		{

			printf("Impossible\n");

			return 0;

		}

		else ans+=1ll*a[i].w;

	printf("%lld\n",ans);

}