学校的网络实在是太次了，网络升级势在必行了，现在每个房间到其他房间都有既有的线路，但是既有线路必须吧网络进行折叠，用以增强其性能，花费是路线长度的一半向上取整，还有一种方案就是走新线路，那么重新走新线路，将耗费测量路程的2倍消费！
改造后的网络必须是接通并且没有回路的！
可能有>n的奇怪数据混入，请注意清理！
第一行两个数
一个数N，表示有多少个房间进行相互连接，一个数M，表示各个房间之间连接情况！
接下来M组数据，每行4个数字u,v,w,z，分别表示房间u到v，连接的网络路线长度为w，z只有1或者是0，1表示u和v原来有线路，0表示重新布线的长度
一个数字，表示总的最小耗费。
3 5 1 2 6 1 1 3 4 1 2 1 4 0 3 2 5 1 2 3 1 0
4
## 提示
5的一种方案就是1-3走老的线路，折叠之后的费用为2，然后走2-3的新线路，因为加倍，费用也是2，所以总共用了4的花费
u_i,v_i \leq N \leq 10000, w_i,M \leq 200000
数据保证每个房间都能连上网络
| 时间限制 | 1 秒 |
| 内存限制 | 128 MB |