题目描述

宁宁现在是一个省的省长，现在她的任务是满足这个省中的每个城市之间的供水需求。

这个省有 $n$ 个城市，每个城市需要 $w_i$ 吨水。

有 $m$ 条输水管道连接这些城市。第 $i$ 个管道连接编号为 $u_i$ 和 $v_i$ 的城市。每条管道都是双向的，它既可以从 $u_i$ 向 $v_i$，也可以从 $v_i$ 向 $u_i$ 输水。

每条供水管道 $i$ 有一个脆弱度 $c_i$。假如有 $f_i$ 吨水流经这条管道，需要支付 $f_i^2 \times c_i$ 的费用用于维护该管道。

有 $k$ 个供水站，第 $i$ 个供水站位于编号为 $s_i$ 的城市。每个供水站都可以提供无限的水。

因为宁宁很可爱，所以你需要帮宁宁求出在满足所有城市的需求情况下，所有管道最小的维护费用。如果存在城市的需求不可能被满足，输出 $-1$。

输入格式

• 第一行三个整数 $n,m,k$。
• 第二行 $n$ 个整数 $w_1,w_2,\dots,w_n$。
• 第三行 $k$ 个整数 $s_1,s_2,\dots,s_k$。
• 接下来 $m$ 行，每行 3 个整数 $u_i,v_i,c_i$。

输出格式

• 一行一个实数，代表最小维护费用。
• 若存在某个城市的需求不可能被满足，输出 $-1$。

本题提供 Special Judge，你的答案若与标准答案的绝对误差或相对误差 $\le 10^{-9}$ 则视为正确。

7 5 2
0 0 0 0 1 1 0
3 1
2 4 1
2 5 2
3 4 2
1 2 1
4 6 1

7 5 3
1 1 4 5 1 4 1
3 1 2
1 2 1
3 4 2
2 4 1
2 5 2
4 6 1

20 20 1
998 704 280 751 455 492 703 35 939 839 64 649 887 730 534 877 274 759 437 926
16
14 12 700
12 15 14
12 7 745
12 8 818
7 9 435
8 5 704
9 18 127
14 11 659
18 6 0
8 4 387
5 2 475
6 19 417
2 1 372
4 17 4
4 10 26
18 13 730
2 20 274
1 16 312
6 18 0
1 3 555

5.75

-0.999999999

213888762681

样例解释

样例 1 中，一种可行的最优方案是：

• 城市 1 向城市 2 输送 $1.25$ 吨水，维护费用为 $1 \times 1.25^2 = 1.5625$。
• 城市 3 向城市 4 输送 $0.75$ 吨水，维护费用为 $2 \times 0.75^2 = 1.125$。
• 城市 2 向城市 4 输送 $0.25$ 吨水，维护费用为 $1 \times 0.25^2 = 0.0625$。
• 城市 2 向城市 5 输送 $1$ 吨水，维护费用为 $2 \times 1^2 = 2$。
• 城市 4 向城市 6 输送 $1$ 吨水，维护费用为 $1 \times 1^2 = 1$。

维护费用共 $5.75$。

样例 2 中，不存在任何可行方案，$-1$ 为正确答案；而 $-0.999999999$ 和 $-1$ 的绝对误差或相对误差 $\le 10^{-9}$，因此也是一种正确输出。

数据范围与提示

Subtask：

• Subtask 1（15 pts）：$k=1$，$m=n-1$，且保证每个城市可以通过若干个水管到达任意一个城市。
• Subtask 2（20 pts）：$k=1$，$m=n$，且保证这 $m$ 个水管将 $n$ 个城市连成了一个环。
• Subtask 3（30 pts）：$1 \le n \le 50$，$0 \le m \le 200$。
• Subtask 4（35 pts）：无特殊限制。

对于 100% 的数据：

• $1 \le n \le 200$
• $0 \le m \le \dfrac{n(n-1)}{2}$
• $1 \le k,s_i,u_i,v_i \le n$
• $0 \le w_i,c_i \le 1000$

可能存在重边、自环。可能存在某个城市有两个以上的供水站。