题意

给定一张 $n$ 个点， $m$ 条边的无向图，有点权 $p_i$ ，边权 $q_i$ 。生成树的权值为

$$\sum_{e\in E}q_e\sum_{u\in\text{inaccessible}(e)}p_u $$

其中 $\text{inaccessible}(e)$ 表示从生成树中删除 $e$ 后，从 $1$ 出发不能到达的结点集合。

求可能的最小权值。

思路

发现从边出发考虑生成树会有瓶颈：选的边并不确定、不知道可以到达边的哪头、点集受树的形态制约。由于每个点都要选（都确定），我们不妨考虑先从点考虑，把式子转化为

$$\sum_{u\in V}p_u\sum_{e\in \text{path}(1\rightarrow u)}q_e $$

豁然开朗，里面的和式正好是从 $1$ 到 $u$ 的距离，显然最短路是最优的。

代码

const int N = 1e5 + 5;

inline ll read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, m;
	int p[N];
	ll dis[N];
	typedef pair<ll, int> P;
	vector<P> e[N];
	priority_queue <P, vector<P>, greater<P> > q;
	void dijkstra() {
		memset(dis, 0x3f, sizeof dis); dis[1] = 0;
		q.emplace(0ll, 1);
		for (int u; !q.empty(); ) {
			P x = q.top(); q.pop();
			if (dis[u = x.second] < x.first) continue;
			for (auto [w, v] : e[u]) 
				if (dis[u] + w <= dis[v]) 
					q.emplace(dis[v] = dis[u] + w, v);
		}
	} 
	int main () {
		n = read(), m = read();
		for (int i = 1; i <= n; ++i) p[i] = read();
		for (int i = 1; i <= m; ++i) {
			int u = read(), v = read(); ll w = read();
			e[u].emplace_back(w, v);
			e[v].emplace_back(w, u);
		}
		
		dijkstra();
		
		ll ans = 0;
		for (int i = 1; i <= n; i++) ans += dis[i] * p[i];
		printf ("%lld\n", ans);
		return 0;
	}
}

int main () {
	string str = "";
//	freopen((str + ".in").c_str(), "r", stdin);
//	freopen((str + ".out").c_str(), "w", stdout);
	Main::main();
	return 0;
}