2989. 孙悟空

【题目描述】

    $Liyuan$想重写著名的《西游记》。在原著中，孙悟空被佛祖困了$500$年，然后被唐僧救起，开始了西行之旅。$Liyuan$认为这对猴子来说太残忍了，所以他改变了故事：

一天，悟空离开家乡——花果山，去参加龙王的宴会，同时，唐僧离开白马寺去灵隐寺演讲。他们都很忙，所以他们会选择最短的路径。然而，在两个地方之间可能存在几个不同的最短路径。现在如来佛祖希望他们在路上相遇。为了增加他们相遇的可能性，佛祖想安排这两条路线使两条路上的公共点尽可能的多。当然，这两条路线应该仍然是最短路径。

    不幸的是，佛祖不擅长算法，所以他请求你的帮助。

【输入格式】

    第一行包含位置$N(1<=N<=500)$的数目和道路$M(1<=M<=N*N)$的数目，用空格隔开。然后是$M$行，每行包含三个整数$a$ $b$ $c$，表示$a$和$b$之间有一条路，其长度是$c(0<c<=10000)$。请注意道路是无向的。最后一行包含四个整数$A$ $B$ $C$ $D$，用空格分隔，分别表示悟空的起点和终点以及唐僧的起点和终点。

【输出格式】

   输出一行，表示两条最短路径的最大公共点个数。

【样例输入】

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

【样例输出】

3

【提示】

一个可能的安排是$（1-2-3-4-6）$是$Wukong$的路线，$（2-3-4）$是唐僧的路线。公共点的个数为$3$；

【来源】

HDU