Language: C++

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

int N, M;
int A[100000];
vector<int> G[100000];
bool used[100000];
multiset<int> ms[100000];

void DFS(int from, int prev, int start) {
  used[from] = true;
  ms[start].insert(A[from]);
  for(int to : G[from]){
    if (to == prev || used[to]) continue;
    DFS(to, from, start);
  }
}

int main() {
  cin >> N >> M;
  if (M + 1 == N) {
    cout << 0 << endl;
    return 0;
  }
  
  for (int i = 0; i < N; ++i) {
    cin >> A[i];
  }
  for (int i = 0; i < M; ++i) {
    int a, b;
    cin >> a >> b;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  
  vector<int> tr;
  for (int i = 0; i < N; ++i) {
    if (used[i]) continue;
    tr.push_back(i);
    DFS(i, -1, i);
  }
  
  long long sum = 0;
  vector<int> v;
  for (int i = 0; i < tr.size(); ++i) {
    multiset<int&> z = ms[tr[i]];
    sum += *z.begin();
    for (auto it = next(z.begin()); it != tr.end(); ++it) {
      v.push_back(*it);
    }
  }
  
  sort(v.begin(), v.end());
  if(v.size() < tr.size() - 2) {
    cout << "Impossible" << endl;
    return 0;
  }
  
  for(int i = 0; i < tr.size() - 2; ++i) {
    sum += v[i];
  }
  cout << sum << endl;
  
  return 0;
}


Compiler output:
In file included from /usr/include/x86_64-linux-gnu/c++/14/bits/c++allocator.h:33,
                 from /usr/include/c++/14/bits/allocator.h:46,
                 from /usr/include/c++/14/string:43,
                 from /usr/include/c++/14/bits/locale_classes.h:40,
                 from /usr/include/c++/14/bits/ios_base.h:41,
                 from /usr/include/c++/14/ios:44,
                 from /usr/include/c++/14/ostream:40,
                 from /usr/include/c++/14/iostream:41,
                 from a.cc:1:
/usr/include/c++/14/bits/new_allocator.h: In instantiation of 'class std::__new_allocator<int&>':
/usr/include/c++/14/bits/allocator.h:128:11:   required from 'class std::allocator<int&>'
  128 |     class allocator : public __allocator_base<_Tp>
      |           ^~~~~~~~~
/usr/include/c++/14/bits/stl_multiset.h:130:22:   required from 'class std::multiset<int&>'
  130 |         rebind<_Key>::other _Key_alloc_type;
      |                             ^~~~~~~~~~~~~~~
a.cc:49:20:   required from here
   49 |     multiset<int&> z = ms[tr[i]];
      |                    ^
/usr/include/c++/14/bits/new_allocator.h:70:26: error: forming pointer to reference type 'int&'
   70 |       typedef _Tp*       pointer;
      |                          ^~~~~~~
/usr/include/c++/14/bits/new_allocator.h:71:26: error: forming pointer to reference type 'int&'
   71 |       typedef const _Tp* const_pointer;
      |                          ^~~~~~~~~~~~~
/usr/include/c++/14/bits/new_allocator.h:126:7: error: forming pointer to reference type 'int&'
  126 |       allocate(size_type __n, const void* = static_cast<const void*>(0))
      |       ^~~~~~~~
/usr/include/c++/14/bits/new_allocator.h:156:7: error: forming pointer to reference type 'int&'
  156 |       deallocate(_Tp* __p, size_type __n __attribute__ ((__unused__)))
      |       ^~~~~~~~~~
/usr/include/c++/14/bits/allocator.h: In instantiation of 'class std::allocator<int&>':
/usr/include/c++/14/bits/stl_multiset.h:130:22:   required from 'class std::multiset<int&>'
  130 |         rebind<_Key>::other _Key_alloc_type;
      |                             ^~~~~~~~~~~~~~~
a.cc:49:20:   required from here
   49 |     multiset<int&> z = ms[tr[i]];
      |                    ^
/usr/include/c++/14/bits/allocator.h:137:26: error: forming pointer to reference type 'int&'
  137 |       typedef _Tp*       pointer;
      |                          ^~~~~~~
/usr/include/c++/14/bits/allocator.h:138:26: error: forming pointer to reference type 'int&'
  138 |       typedef const _Tp* const_pointer;
      |                          ^~~~~~~~~~~~~
In file included from /usr/include/c++/14/ext/alloc_traits.h:34,
                 from /usr/include/c++/14/bits/basic_string.h:39,
                 from /usr/include/c++/14/string:54:
/usr/include/c++/14/bits/alloc_traits.h: In instantiation of 'struct std::allocator_traits<std::allocator<int&> >':
/usr/include/c++/14/ext/alloc_traits.h:45:10:   required from 'struct __gnu_cxx::__alloc_traits<std::allocator<int&>, int&>'
   45 |   struct __alloc_traits
      |          ^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_multiset.h:130:22:   required from 'class std::multiset<int&>'
  130 |         rebind<_Key>::other _Key_alloc_type;
      |                             ^~~~~~~~~~~~~~~
a.cc:49:20:   required from here
   49 |     multiset<int&> z = ms[tr[i]];
      |                    ^
/usr/include/c++/14/bits/alloc_traits.h:470:13: error: forming pointer to reference type 'int&'
  470 |       using pointer = _Tp*;
      |             ^~~~~~~
/usr/include/c++/14/bits/alloc_traits.h:473:13: error: forming pointer to reference type 'int&'
  473 |       using const_pointer = const _Tp*;
      |             ^~~~~~~~~~~~~
/usr/include/c++/14/ext/alloc_traits.h: In instantiation of 'struct __gnu_cxx::__alloc_traits<std::allocator<int&>, int&>':
/usr/include/c++/14/bits/stl_multiset.h:130:22:   required from 'class std::multiset<int&>'
  130 |         rebind<_Key>::other _Key_alloc_type;
      |                             ^~~~~~~~~~~~~~~
a.cc:49:20:   required from here
   49 |     multiset<int&> z = ms[tr[i]];
      |                    ^
/usr/include/c++/14/ext/alloc_traits.h:61:23: error: 'allocate' has not been declared in '__gnu_cxx::__alloc_traits<std::allocator<int&>, int&>::_Base_type'
   61 |     using _Base_type::allocate;
      |                       ^~~~~~~~
/usr/include/c++/14/ext/alloc_traits.h:62:23: error: 'deallocate' has not been declared in '__gnu_cxx::__alloc_traits<std::allocator<int&>, int&>::_Base_type'
   62 |     using _Base_type::deallocate;
      |                       ^~~~~~~~~~
In file included from /usr/include/c++/14/set:62,
                 from a.cc:3:
/usr/include/c++/14/bits/stl_tree.h: In instantiation of 'class std::_Rb_tree<int&, int&, std::_Identity<int&>, std::less<int&>, std::allocator<int&> >':
/usr/include/c++/14/bits/stl_multiset.h:135:17:   required from 'class std::multiset<int&>'
  135 |       _Rep_type _M_t;
      |                 ^~~~
a.cc:49:20:   required from here
   49 |     multiset<int&> z = ms[tr[i]];
      |                    ^
/usr/include/c++/14/bits/stl_tree.h:536:49: error: forming pointer to reference type 'std::_Rb_tree<int&, int&, std::_Identity<int&>, std::less<int&>, std::allocator<int&> >::value_type' {aka 'int&'}
  536 |       typedef value_type*                       pointer;
      |                                                 ^~~~~~~
/usr/include/c++/14/bits/stl_tree.h:537:49: error: forming pointer to reference type 'std::_Rb_tree<int&, int&, std::_Identity<int&>, std::less<int&>, std::allocator<int&> >::value_type' {aka 'int&'}
  537 |       typedef const value_type*                 const_pointer;
      |                                                 ^~~~~~~~~~~~~
In file included from /usr/include/c++/14/set:64:
/usr/include/c++/14/bits/stl_multiset.h: In instantiation of 'class std::multiset<int&>':
a.cc:49:20:   required from here
   49 |     multiset<int&> z = ms[tr[i]];
      |                    ^
/usr/include/c++/14/bits/stl_multiset.h:509:7: error: 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(value_type&&) [with _Key = int&; _Compare = std::less<int&>; _Alloc = std::allocator<int&>; iterator = std::_Rb_tree<int&, int&, std::_Identity<int&>, std::less<int&>, std::allocator<int&> >::const_iterator; value_type = int&]' cannot be overloaded with 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(const value_type&) [with _Key = int&; _Compare = std::less<int&>; _Alloc = std::allocator<int&>; iterator = std::_Rb_tree<int&, int&, std::_Identity<int&>, std::less<int&>, std::allocator<int&> >::const_iterator; value_type = int&]'
  509 |       insert(value_type&& __x)
      |       ^~~~~~
/usr/include/c++/14/bits/stl_multiset.h:504:7: note: previous declaration 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(const value_type&) [with _Key = int&; _Compare = std::less<int&>; _Alloc = std::allocator<int&>; iterator = std::_Rb_tree<int&, int&, std::_Identity<int&>, std::less<int&>, std::allocator<int&> >::const_iterator; value_type = int&]'
  504 |       insert(const value_type& __x)
      |       ^~~~~~
/usr/include/c++/14/bits/stl_multiset.h:539:7: error: 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(const_iterator, value_type&&) [with _Key = int&; _Compare = std::less<int&>; _Alloc = std::allocator<int&>; iterator = std::_Rb_tree<int&, int&, std::_Identity<int&>, std::less<int&>, std::allocator<int&> >::const_iterator; const_iterator = std::_Rb_tree<int&, int&, std::_Identity<int&>, std::less<int&>, std::allocator<int&> >::const_iterator; value_type = int&]' cannot be overloaded with 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(const_iterator, const value_type&) [with _Key = int&; _Compare = std::less<int&>; _Alloc = std::allocator<int&>; iterator = std::_Rb_tree<int&, int&, std::_Identity<int&>, std::less<int&>, std::allocator<int&> >::const_iterator; const_iterator = std::_Rb_tree<int&, int&, std::_Identity<int&>, std::less<int&>, std::allocator<int&> >::const_iterator; value_type = int&]'
  539 |       insert(const_iterator __position, value_type&& __x)
      |       ^~~~~~
/usr/include/c++/14/bits/stl_multiset.h:534:7: note: previous declaration 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(const_iterator, const value_type&) [with _Key = int&; _Compare = std::less<int&>; _Alloc = std::allocator<int&>; iterator = std::_Rb_tree<int&, int&, std::_Identity<int&>, std::less<int&>, std::allocator<int&> >::const_iterator; const_iterator = std::_Rb_tree<int&, int&, std::_Identity<int&>, std::less<int&>, std::allocator<int&> >::const_iterator; value_type = int&]'
  534 |       insert(const_iterator __position, const value_type& __x)
      |       ^~~~~~
a.cc: In function 'int main()':
a.cc:49:32: error: conversion from 'multiset<int>' to non-scalar type 'multiset<int&>' requested
   49 |     multiset<int&> z = ms[tr[i]];
      |                        ~~~~~~~~^
/usr/include/c++/14/bits/stl_tree.h: In instantiation of 'struct std::_Rb_tree_const_iterator<int&>':
a.cc:50:20:   required from here
   50 |     sum += *z.begin();
      |             ~~~~~~~^~
/usr/include/c++/14/bits/stl_tree.h:328:26: error: forming pointer to reference type 'int&'
  328 |       typedef const _Tp* pointer;
      |                          ^~~~~~~
a.cc:51:24: error: no matching function for call to 'next(std::multiset<int&>::iterator)'
   51 |     for (auto it = next(z.begin()); it != tr.end(); ++it) {
      |                    ~~~~^~~~~~~~~~~
In file included from /usr/include/c++/14/string:47:
/usr/include/c++/14/bits/stl_iterator_base_funcs.h:232:5: note: candidate: 'template<class _InputIterator> constexpr _InputIterator std::next(_InputIterator, typename iterator_traits<_Iter>::difference_type)'
  232 |     next(_InputIterator __x, typename
      |     ^~~~
/usr/include/c++/14/bits/stl_iterator_base_funcs.h:232:5: note:   template argument deduction/sub