雪拉比的求救
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

爱与正义的火箭队为了得到雪拉比，于是对它展开了捕捉计划。当雪拉比受到伤害时，它会使用全部能力穿越到1小时之后的时间，并发出了SOS的求救。
小梁在旅行的途中感受到了雪拉比的求救，她跟着雪拉比的求救，来到了一座遗迹，该遗迹的俯视图可看为个传送点，条道路所组成的双向连通图，每一条道路都有对应的长度。
通过心灵指引小梁终于救出了雪拉比。但是由于被火箭队追赶，雪拉比只能隐藏自己的气息。
火箭队也发现了雪拉比和小梁的位置，同时小梁也在雪拉比的帮助下确定了火箭队的位置。小梁想知道在她和火箭队移动速度相同的条件下，为了顺利的躲避火箭队，并且双方都以最短路径向对方原始位置移动，有多少方案可以使得他们不相遇，并对方案数取模。

输入描述:

第一行输入两个整数和
第二行输入两个整数和分别表示小梁和火箭队所在的位置
下面M行输入三个整数 u_i, v_i, d_i 表示第u_i个点和第v_i个点相连，他们的距离是

输出描述:

输出所有符合条件的方案对取模后的数。
示例1

输入

复制 
8 9
4 2
1 2 2
7 6 9
2 8 12
4 2 18
8 4 2
3 5 18
1 5 3
4 7 7
2 7 7

输出

复制 
2

说明

4和2之间的最短路为14，其中不会相遇的方案路线分别为：
①T到S：2-8-4；S到T：4-7-2
②T到S：2-7-4；S到T：4-8-2