题目

题目描述

在米国有一所大学，名叫万国歌剧与信息大学（Universal Opera and Informaticas University）。简称UOI大学。UOI大学的建筑与道路分布很有趣，每对建筑之间有且仅有一条直接或者间接的路径相连，更加明确的说，就是成树形分布。 其实在设计时，对于大学的$N$个建筑，总共有$M$条道路可以修建，每条道路都有一个距离值$Dist_i$和一个美学值$Value_i$。一个设计方案的距离值和美学值定义为该设计方案内包含的道路的距离值与美学值之和。投资方的要求只有设计方案的距离值最小。

大神出于对树的喜爱所以决定设计方案必须是一棵树。 因为要参加UOI，所以当时大神就急急忙忙地随机选择了一个合法的方案。但其实存在很多合法的方案,假设每种设计方案取的概率是均等的，那么设计方案的美学值期望是多少？

输入

第一行两个整数，$N$和$M$，意义如上所述。

第二行到第$M+1$行，每行$4$个整数，$X_i, Y_i, Dist_i, Value_i$，分别表示这条道路连接的两个建筑的编号，距离值以及美学值。

输入保证至少有一种合法方案。

输出

一行一个整数，即满足总道路长度最小的情况下，设计方案的美学值期望。 要求保留$5$位小数。

样例输入

2 1
1 2 3 4

样例输出

4.00000

数据范围

$10\%$的数据保证$N \leq 10, M \leq 20$；

$30\%$的数据保证$N \leq 100, M \leq 1000$；

$100\%$的数据保证$N \leq 1000, M \leq 200000$；

$10\%$的数据保证$M=N-1$；

$20\%$的数据保证距离值相同的道路数小于$10$；

$100\%$的数据保证距离值相同的道路数小于$30$，同时不保证没有重边。