问题描述

上文说到，小徐在玩一款新潮的游戏，现在，他要抽卡。

小徐的抽卡池目前有 $n$ 张卡牌，编号为从 1 到 $n$，小徐想抽到这 $n$ 张卡牌中编号为 $n$ 的那张卡牌，他会一直抽卡直到抽中 $n$ 号卡牌，抽到即立刻结束抽卡。

不同的两张卡牌之间可能具有"联通关系" , "联通关系"的定义为: 抽到 $i$ 号牌之后下一轮有可能抽到 $j$号牌 , 同时抽到 $j$ 号牌之后下一轮也有可能抽到 $i$ 号牌 , 若一张卡牌与多张卡牌具有"联通关系" , 则抽到这多张具有"联通关系"的卡牌的概率是相等的 , 但如果两张卡牌不具有"联通关系" , 则抽到其中一张卡牌后的下一轮绝对不会抽到另一张卡牌 。举例说明：若2号牌和3、4号牌都具有"联通关系"且只和3、4号牌具有"联通关系", 则抽到2号卡牌后下一张只可能抽到3号或4号卡牌 , 而抽到这两张牌的概率都为二分之一。

在游戏中，游戏的管理者会给出 $q$ 个"联通关系"，每个"联通关系"包含三个整数 $a_i, b_i, c_i$，它们分别表示以下含义： $a_i$ 和 $b_i$ 建立"联通关系" , 同时若抽卡时触发这 一"联通关系"，即先抽 $a_i$ 再抽 $b_i$，或先抽 $b_i$ 再抽 $a_i$，则会耗费 $c_i$ 的代价。友情提示：游戏的管理者不会让一张卡牌与自己建立契约关系，且这 $q$ 个"联通关系"会保证 所有卡牌都有被抽到的可能。

为了让小徐再抽到 $n$ 号卡牌时耗费尽可能少的代价，小石（迷弟之一）再次打开了外挂，他可以重新分配每个"联通关系"触发时的代价, 但是为了不被发现 , 小石也只能将某个代价与其他已有的代价进行交换，不能自行设定新的代价值。

现在，请你对这 $q$ 个代价进行重新分配，使小徐在获得第 $n$ 张卡牌时消耗的代价的期望值最小。

输入格式

第一行是两个整数 $n$ 和 $q$ , 分别代表卡牌的数量和"联通关系"的数量。

接下来的 $q$ 行 , 每行给出两个数 $a_i$ 和 $b_i$ ($a_i$ ≠ $b_i$) , 表示 $a_i$ 号卡牌和 $b_i$ 号卡牌将建立"联通关系"。

在第 $q + 2$ 行给出 $q$ 个数，第 $i$ 个数 $c_i$ 表示第 $i$ 个"联通关系"触发时花费的代价。

输出格式

输出一个实数，表示对这 $q$ 个代价进行重新分配后，小徐获得 $n$ 号卡牌时消耗的代价的最小期望值，当你的答案与标准答案之间的绝对误差或相对误差小于 $10^{-6}$ 时视作正确。

输入样例

3 2
1 2
2 3
2 2

输出样例

8.00000000

评测数据规模

对于所有评测数据： $2 \le n \le 500$ , $n - 1 \le q \le \frac{n·(n - 1)}{2}$, $1 \le a_i , b_i \le n$，$1 \le c_i \le 10^4$。