Language: C++

#include <bits/stdc++.h>

template<class EdgeInfo>
class Graph {
protected:
	using size_type = ::std::size_t;
	struct Edge {
		size_type to;
		EdgeInfo info;
		Edge() : to(-1) {}
		Edge(size_type to_, EdgeInfo info_) : to(to_), info(info_) {}
	};
	using edge_type = Edge;

	::std::vector<::std::vector<edge_type>> edges;

public:
	Graph() {}
	Graph(size_type n) : edges(n) {}
	Graph(const Graph& g) : edges(g.edges) {}
	Graph(Graph&& g) { ::std::swap(edges, g.edges); }
	Graph& operator=(const Graph& g) { edges = g.edges; }
	Graph& operator=(Graph&& g) noexcept { ::std::swap(edges, g.edges); }

	const size_type size() { return edges.size(); }
	virtual void add_edge (size_type from, size_type to, EdgeInfo info) = 0;

	const ::std::vector<edge_type>& operator[](size_type k) { return edges[k]; }

};

template<class EdgeInfo>
class UndirectedGraph : public Graph<EdgeInfo> {
protected:
	using size_type = ::std::size_t;
public:
	using edge_type = typename Graph<EdgeInfo>::edge_type;
	UndirectedGraph() {}
	UndirectedGraph(size_type n) : Graph<EdgeInfo>(n) {}
	UndirectedGraph(const UndirectedGraph& g) : Graph<EdgeInfo>(g) {}
	UndirectedGraph(UndirectedGraph&& g) : Graph<EdgeInfo>(g) {}
	UndirectedGraph& operator=(const UndirectedGraph& g) { this->edges = g.edges; return *this;}
	UndirectedGraph& operator=(UndirectedGraph&& g) noexcept { ::std::swap(this->edges, g.edges); return *this; }

	void add_edge (size_type from, size_type to, EdgeInfo info = EdgeInfo()) {
		this->edges[from].push_back(edge_type(to, info));
		this->edges[to].push_back(edge_type(from, info));
	}
};

class UnionFind{
private:
	::std::vector<int_fast32_t> par;
	size_t n;

public:
	UnionFind(){}
	UnionFind(size_t n):n(n){
		par.resize(n, -1);
	}

	uint_fast32_t find(uint_fast32_t x){
		return par[x] < 0 ? x : par[x] = find(par[x]);
	}

	size_t size(uint_fast32_t x){
		return -par[find(x)];
	}

	bool unite(uint_fast32_t x, uint_fast32_t y){
		x = find(x);
		y = find(y);
		if(x == y) return false;
		if(size(x) < size(y)) std::swap(x, y);
		par[x] += par[y];
		par[y] = x;
		return true;
	}

	bool same(uint_fast32_t x, uint_fast32_t y){
		return find(x) == find(y);
	}
};

template<class EdgeWeight>
class Kruskal {
private:
	using size_type = ::std::size_t;
	using weight_type = EdgeWeight;

public:
	struct edge_info {
		size_type from;
		weight_type w;
		edge_info() {}
		edge_info(size_type f_, weight_type w_) : from(f_), w(w_) {}
	};

private:
	using Graph = UndirectedGraph<edge_info>;
	using edge_type = typename Graph::edge_type;

	Graph graph;
	weight_type weight_sum;
public:
	Kruskal() {}
	Kruskal(size_type n) : graph(n) {}
	Kruskal(const Graph& g) : graph(g) {}
	Kruskal(Graph&& g) : graph(g) {}

	void add_edge(size_type from, size_type to, weight_type w) {
		graph.add_edge(from, to, edge_info(from, w));
	}

	const Graph& build(size_type N, const ::std::vector<edge_type>& edges) {
		UnionFind uf(N);
		Graph mst = Graph(graph.size());
		weight_sum = weight_type();

		::std::sort(edges.begin(), edges.end(),
			[](const edge_type& lhs, const edge_type& rhs) {
				return lhs.info.w < rhs.info.w;
			}
		);

		for (auto edge : edges) {
			if (uf.same(edge.info.from, edge.to)) continue;
			uf.unite(edge.info.from, edge.to);
			mst.add_edge(edge.info.from, edge.to, edge.info);
			weight_sum = weight_sum + edge.info.w;
		}
		return graph = mst;
	}

	const Graph& build() {
		::std::vector<edge_type> edges;

		for (size_type i = 0; i < graph.size(); i++) {
			for (auto edge : graph[i]) {
				edges.push_back(edge);
			}
		}
		return build(graph.size(), edges);
	}

	const weight_type& weight() { return weight_sum; }
};

template<class EdgeWeight>
class VoronoiMST {
private:
	using size_type = ::std::size_t;
	using weight_type = EdgeWeight;

	using edge_info = typename Kruskal<weight_type>::edge_info;
	using Graph = UndirectedGraph<edge_info>;

	Graph graph;
	weight_type weight_sum;
public:
	VoronoiMST() {}
	VoronoiMST(size_type n) : graph(n) {}
	VoronoiMST(const Graph& g) : graph(g) {}
	VoronoiMST(Graph&& g) : graph(g) {}

	void add_edge(size_type from, size_type to, const weight_type w) {
		graph.add_edge(from, to, edge_info(from, w));
	}

	const Graph& build(const ::std::vector<::std::int64_t>& base) {
		::std::vector<size_type> base_(base.begin(), base.end());
		return build(base_);
	}

	const Graph& build(const ::std::vector<size_type>& base) {
		::std::vector<weight_type> ws(graph.size());
		::std::vector<size_type> visit(graph.size(), -1);

		for (auto x : base) {
			assert(0 <= x && x < base.size());
		}
		Kruskal<weight_type> kr(base.size());

		using P = ::std::tuple<weight_type, size_type, size_type>;
		::std::priority_queue<P, ::std::vector<P>, ::std::greater<P>> pq;

		for (auto x : base) {
			pq.push(P(0, x, x));
		}

		while (pq.size()) {
			weight_type w;
			size_type u, src;
			::std::tie(w, u, src) = pq.top(); pq.pop();
			if (visit[u] == -1) {
				visit[u] = src;
				ws[u] = w;
				for (auto &v : graph[u]) {
					pq.push(P(w + v.info.w, v.to, src));
				}
			} else if (visit[u] < src) {
				kr.add_edge(src, visit[u], w + ws[u]);
			}
		}
		graph = kr.build();
		weight_sum = kr.weight();

		return graph;
	}

	const weight_type& weight() { return weight_sum; }
};


int main(void) {
	using namespace std;
	int64_t N, D;
	cin >> N;
	vector<int64_t> X(N);
	for (auto &x : X) cin >> x;
	VoronoiMST<int64_t> mst(2*N);
	for (int64_t i = 0; i < N; i++) {
		mst.add_edge(i, i+N, X[i]);
	}
	for (int64_t i = 0; i < N-1; i++) {
		int64_t a, b, c;
		cin >> a >> b >> c; a--; b--;
		mst.add_edge(a+N, b+N, c);
	}
	vector<int64_t> st(N);
	iota(st.begin(), st.end(), 0);
	auto g = mst.build(st);
	cout << mst.weight() << endl;
}
/*

	Voronoi MST

	- class EdgeWeight
		辺の重み
		
		要求
			- operator<
			- operator+
			- operator=

	提供
		- constructor
			- 頂点数，Graphのいずれかで初期化できる

		- add_edge(size_type u, size_type v, EdgeWeight w )
			- u <-> vと結ぶ重みwの無向辺を追加する

		- build(vector<size_type> v) -> Graph
			- 現在のGraphの頂点でvに含まれるものを頂点とする最小全域森を構築し，返す

		- weight -> EdgeWeight
			- 最後に構築した最小全域森の重みを返す
*/


Compiler output:
In file included from /usr/include/c++/14/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_algo.h: In instantiation of 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<const Graph<Kruskal<long int>::edge_info>::Edge*, vector<Graph<Kruskal<long int>::edge_info>::Edge, allocator<Graph<Kruskal<long int>::edge_info>::Edge> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<Kruskal<long int>::build(size_type, const std::vector<Graph<edge_info>::Edge, std::allocator<Graph<edge_info>::Edge> >&)::<lambda(const Kruskal<long int>::edge_type&, const Kruskal<long int>::edge_type&)> >]':
/usr/include/c++/14/bits/stl_algo.h:1817:25:   required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<const Graph<Kruskal<long int>::edge_info>::Edge*, vector<Graph<Kruskal<long int>::edge_info>::Edge, allocator<Graph<Kruskal<long int>::edge_info>::Edge> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<Kruskal<long int>::build(size_type, const std::vector<Graph<edge_info>::Edge, std::allocator<Graph<edge_info>::Edge> >&)::<lambda(const Kruskal<long int>::edge_type&, const Kruskal<long int>::edge_type&)> >]'
 1817 |           std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1908:31:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<const Graph<Kruskal<long int>::edge_info>::Edge*, vector<Graph<Kruskal<long int>::edge_info>::Edge, allocator<Graph<Kruskal<long int>::edge_info>::Edge> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<Kruskal<long int>::build(size_type, const std::vector<Graph<edge_info>::Edge, std::allocator<Graph<edge_info>::Edge> >&)::<lambda(const Kruskal<long int>::edge_type&, const Kruskal<long int>::edge_type&)> >]'
 1908 |           std::__final_insertion_sort(__first, __last, __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:4805:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<const Graph<Kruskal<long int>::edge_info>::Edge*, vector<Graph<Kruskal<long int>::edge_info>::Edge, allocator<Graph<Kruskal<long int>::edge_info>::Edge> > >; _Compare = Kruskal<long int>::build(size_type, const std::vector<Graph<edge_info>::Edge, std::allocator<Graph<edge_info>::Edge> >&)::<lambda(const Kruskal<long int>::edge_type&, const Kruskal<long int>::edge_type&)>]'
 4805 |       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
      |       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:120:14:   required from 'const Kruskal<EdgeWeight>::Graph& Kruskal<EdgeWeight>::build(size_type, const std::vector<typename UndirectedGraph<edge_info>::edge_type>&) [with EdgeWeight = long int; Graph = UndirectedGraph<Kruskal<long int>::edge_info>; size_type = long unsigned int; typename UndirectedGraph<edge_info>::edge_type = Graph<Kruskal<long int>::edge_info>::Edge]'
  120 |                 ::std::sort(edges.begin(), edges.end(),
      |                 ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
  121 |                         [](const edge_type& lhs, const edge_type& rhs) {
      |                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  122 |                                 return lhs.info.w < rhs.info.w;
      |                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  123 |                         }
      |                         ~   
  124 |                 );
      |                 ~           
a.cc:143:15:   required from 'const Kruskal<EdgeWeight>::Graph& Kruskal<EdgeWeight>::build() [with EdgeWeight = long int; Graph = UndirectedGraph<Kruskal<long int>::edge_info>]'
  143 |                 return build(graph.size(), edges);
      |                        ~~~~~^~~~~~~~~~~~~~~~~~~~~
a.cc:205:19:   required from 'const VoronoiMST<EdgeWeight>::Graph& VoronoiMST<EdgeWeight>::build(const std::vector<long unsigned int>&) [with EdgeWeight = long int; Graph = UndirectedGraph<Kruskal<long int>::edge_info>]'
  205 |                 graph = kr.build();
      |                         ~~~~~~~~^~
a.cc:172:15:   required from 'const VoronoiMST<EdgeWeight>::Graph& VoronoiMST<EdgeWeight>::build(const std::vector<long int>&) [with EdgeWeight = long int; Graph = UndirectedGraph<Kruskal<long int>::edge_info>]'
  172 |                 return build(base_);
      |                        ~~~~~^~~~~~~
a.cc:232:20:   required from here
  232 |         auto g = mst.build(st);
      |                  ~~~~~~~~~^~~~
/usr/include/c++/14/bits/stl_algo.h:1782:24: error: passing 'const Graph<Kruskal<long int>::edge_info>::Edge' as 'this' argument discards qualifiers [-fpermissive]
 1782 |               *__first = _GLIBCXX_MOVE(__val);
      |                        ^
a.cc:7:16: note:   in call to 'constexpr Graph<Kruskal<long int>::edge_info>::Edge& Graph<Kruskal<long int>::edge_info>::Edge::operator=(Graph<Kruskal<long int>::edge_info>::Edge&&)'
    7 |         struct Edge {
      |                ^~~~
In file included from /usr/include/c++/14/bits/stl_algo.h:61:
/usr/include/c++/14/bits/stl_heap.h: In instantiation of 'void std::__pop_heap(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<const Graph<Kruskal<long int>::edge_info>::Edge*, vector<Graph<Kruskal<long int>::edge_info>::Edge, allocator<Graph<Kruskal<long int>::edge_info>::Edge> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<Kruskal<long int>::build(size_type, const std::vector<Graph<edge_info>::Edge, std::allocator<Graph<edge_info>::Edge> >&)::<lambda(const Kruskal<long int>::edge_type&, const Kruskal<long int>::edge_type&)> >]':
/usr/include/c++/14/bits/stl_algo.h:1596:19:   required from 'void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<const Graph<Kruskal<long int>::edge_info>::Edge*, vector<Graph<Kruskal<long int>::edge_info>::Edge, allocator<Graph<Kruskal<long int>::edge_info>::Edge> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<Kruskal<long int>::build(size_type, const std::vector<Graph<edge_info>::Edge, std::allocator<Graph<edge_info>::Edge> >&)::<lambda(const Kruskal<long int>::edge_type&, const Kruskal<long int>::edge_type&)> >]'
 1596 |           std::__pop_heap(__first, __middle, __i, __comp);
      |           ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1868:25:   required from 'void std::__partial_sort(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<const Graph<Kruskal<long int>::edge_info>::Edge*, vector<Graph<Kruskal<long int>::edge_info>::Edge, allocator<Graph<Kruskal<long int>::edge_info>::Edge> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<Kruskal<long int>::build(size_type, const std::vector<Graph<edge_info>::Edge, std::allocator<Graph<edge_info>::Edge> >&)::<lambda(const Kruskal<long int>::edge_type&, const Kruskal<long int>::edge_type&)> >]'
 1868 |       std::__heap_select(__first, __middle, __last, __comp);
      |       ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1884:27:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<const Graph<Kruskal<long int>::edge_info>::Edge*, vector<Graph<Kruskal<long int>::edge_info>::Edge, allocator<Graph<Kruskal<long int>::edge_info>::Edge> > >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<Kruskal<long int>::build(size_type, const std::vector<Graph<edge_info>::Edge, std::allocator<Graph<edge_info>::Edge> >&)::<lambda(const Kruskal<long int>::edge_type&, const Kruskal<long int>::edge_type&)> >]'
 1884 |               std::__partial_sort(__first, __last, __last, __comp);
      |               ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1905:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<const Graph<Kruskal<long int>::edge_info>::Edge*, vector<Graph<Kruskal<long int>::edge_info>::Edge, allocator<Graph<Kruskal<long int>::edge_info>::Edge> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<Kruskal<long int>::build(size_type, const std::vector<Graph<edge_info>::Edge, std::allocator<Graph<edge_info>::Edge> >&)::<lambda(const Kruskal<long int>::edge_type&, const Kruskal<long int>::edge_type&)> >]'
 1905 |           std::__introsort_loop(__first, __last,
      |           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
 1906 |                                 std::__lg(__last - __first) * 2,
      |                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 1907 |                                 __comp);
      |                                 ~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:4805:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<const Graph<Kruskal<long int>::edge_info>::Edge*, vector<Graph<Kruskal<long int>::edge_info>::Edge, allocator<Graph<Kruskal<long int>::edge_info>::Edge> > >; _Compare = Kruskal<long int>::build(size_type, const std::vector<Graph<edge_info>::Edge, std::allocator<Graph<edge_info>::Edge> >&)::<lambda(const Kruskal<long int>::edge_type&, const Kruskal<long int>::edge_type&)>]'
 4805 |       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
      |       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:120:14:   required from 'const Kruskal<EdgeWeight>::Graph& Kruskal