小明所在 A 国家很穷，城市之间的道路都是几百年前修的路，再加上几天前 A 国家爆发了洪水，冲坏了好多条道路，现在国王想要从 X 城市去往 Y 城市，要求尽快恢复一些道路使得两座城市连通，因为国王很穷，所以要求修复的道路长度尽可能少。现在他把这个任务交给了小明，小明很是苦恼，聪明的你可以帮助小明解决这个问题吗？

第一行包括两个数字 n,m ，分别表示城市的个数与道路的条数；

之后 m 行，每行四个数字 u,v,w,k表示城市  u与 v之间的一条长w  的路径， k=1表示路径已损坏， k=0 表示未损坏；

最后一行输入两个数字 u,v ，表示需要恢复连通的两个城市。

其中 1\leq n \leq 10000，  n-1 \leq m \leq 100000 ，城市编号从 1 开始。

输出一个整数，表示恢复 i 城市与 j 城市的交通需要修复道路长度的最小值。

对于 10\% 的数据， 1 \leq n \leq 4 ；

对于 50\% 的数据， 1 \leq n \leq 1024 ；

对于 100\% 的数据， 1 \leq n \leq 10000 ， 1 \leq m \leq 100000 ；城市编号从 1开始。