该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

潘皇正兴高采烈地走在去实验室的路上，心里盘算着今天又能抓到几个迟到的倒霉蛋。潘皇不知道的是，Frank早已在他的必经之路上设下陷阱，为迟到的阿冬争取时间。

随着一声りょういきてんかい（领域展开），Frank瞬间消失在了阴影之中，只留下了潘皇被困在了一个由符文构成的封印之中。

潘皇对着符文一通分析，发现符文共有$N$个魔核和$M$条魔力通路，魔核之间由魔力通路连接。每个魔核启动后会释放出每个魔核的专属魔力，任何魔核的魔力流经任意一条魔力通路的时间均为1，魔力在到达其它魔核后仍会继续流经其它魔力通路，且不同魔核之间的魔力不会相互干扰。为了困住潘皇更长时间，Frank添加了一些无关紧要的魔力通路。现在潘皇需要打破尽可能多的无用的魔力通路才能知道初始符文是什么，以便破除封印。

Frank并不想把潘皇困死，他留下了一张纸条，让潘皇知道破除封印必须满足以下条件之一：

• 在启动魔核$s_1$后，$s_1$的魔力要能在不超过$l_1$的时间内流到魔核$t_1$，并且启动魔核$s_2$后，$s_2$的魔力要能在不超过$l_2$的时间内使魔力流到魔核$t_2$。在此基础上潘皇需要摧毁尽可能多的魔力通路(摧毁魔力通路之后部分魔核之间可以不连通)。

• 若摧毁任意一条魔力通路之前上述条件就无法达到，则潘皇需要女装才能破除封印。

现在你要帮助潘皇求出他需要摧毁多少条魔力通路才能破除封印；若他需要女装才能破除封印，请直接输出$-1$。

输入格式

第一行两个整数$N,M$($1 \le N,M \le 3000$)，表示魔核数目和魔力通路数目，魔核从$1$到$N$编号。

接下来$M+2$行，前$M$行每行两个整数$u,v(1 \le u,v \le N且u=\not v)$，表示一条连接魔核$u,v$的魔力通路。保证两个魔核之间不存在多于一条的直接相连的魔力通路。

后$2$行，每行三个整数$s_i,t_i,l_i(1\le s_i,t_i\le N,0 \le l_i \le N)$。倒数第二行表示$s_1,t_1,l_1$；最后一行表示$s_2,t_2,l_2$。

输出格式

输出一个整数，表示答案。

样例

5 4
1 2
2 3
3 4
4 5
1 3 2
2 4 2

1