conquest.cc

#include <bits/stdc++.h>

using namespace std;

struct MinHeap {
	bool operator()(pair<int, int> a, pair<int, int> b) {
		return a.second > b.second;
	}
};

int bfs(vector<vector<int>>& M, vector<int>& lookup) {
	priority_queue<pair<int,int>, std::vector<pair<int,int>>, MinHeap> min_heap;
	vector<bool> visited(M.size(), false);	
	min_heap.push({0, lookup[0]});

	int total = lookup[0];
	bool first = true;
	while(!min_heap.empty()) {
		int top = min_heap.top().first; min_heap.pop();
		if(total > lookup[top])
			total += lookup[top];
		else if(!first) break;
		visited[top] = true;
		first = false;
		vector<int> neighbours = M[top];
		for(auto it = neighbours.begin(); it != neighbours.end(); ++it) {
			int neighbour = *it;
			if(visited[neighbour]) continue;
			min_heap.push({neighbour, lookup[neighbour]});
		}
	}
	return total;
}

int main() {
	int n, m;
	cin >> n >> m;

	vector<vector<int>> mat(n);

	vector<int> lookup(n);

	for(int x{}; x < m; ++x) {
		int u, v;
		cin >> u >> v;
		u--; v--;
		mat[u].push_back(v);
		mat[v].push_back(u);
	}
	for(int x{}; x < n; ++x) {
		int score;
		cin >> score;
		lookup[x] = score;
	}

	int res = bfs(mat, lookup);
	cout << res << endl;


	return 0;
}