82703 - Sightseeing

旅游运营商 Your Personal Holiday 组织比荷卢经济联盟的导游巴士旅行。每天，巴士都会从一个城市 S 行驶到另一个城市 F 。在这条路上，巴士上的游客可以看到沿途的景点。此外，公共汽车在一些美丽的城市停靠了几站（零站或更多站），游客们可以在那里下车欣赏当地的风景。

不同的游客群体可能对他们想看的景点有不同的偏好，因此对从 S 到 F 的路线也有不同的喜好。因此，Your Personal Holiday 希望为客户提供许多不同路线的选择。由于酒店已提前预订，出发城市 S 和最终城市 F 是固定的。如果从城市 A 到城市 B 的两条路线只要经过一条不同的道路，则认为从 S 到 F 的两条路线是不同的。

游客可以选择的路线有限制。为了在车站有足够的时间观光，公共汽车必须从 S 到 F 走一条短途路线。它必须是一条距离最小的路线，或者是一条比最小距离长一个距离单位的路线。事实上，通过允许延长一个距离单位的路线，游客可能比将他们限制在最短的路线上有更多的选择。这增强了个人假期的印象。

例如，对于上述路线图，从 S=1 到 F=5 有两条最小路线：1→2→5 和 1→3→5，长度均为 6 。有一条路线长一个距离单位：1→3→4→5，长度为 7。

现在，给定比荷卢经济联盟和两个城市 S 和 F 的部分路线图，旅游运营商 Your Personal Holiday 想知道在上述路线长度限制下，它可以为客户提供多少条不同的路线。

输入文件的第一行包含一个数字：要遵循的测试用例的数量。每个测试用例都有以下格式：

• 一条由两个整数 N 和 M 组成的线，用一个空格隔开，2≤N≤1000，1≤M≤10000：路线图中的城市数量和道路数量。

• M 条线，每条线有三个整数 A、B 和 L，由单个空格分隔，1≤A,B≤N，A \ne B，1≤L≤1000，描述了一条从 A 市到 B 市的长度为 L 的道路。这些道路是单向的。因此，如果有一条从 A 到 B 的路，那么从 B 到 A 就不一定也有路。从 A 市到 B 市可能有不同的路。

• 一条有两个整数 S 和 F 的线，用一个空格隔开，1≤S,F≤N，S \ne F ：路线的起点城市和终点城市。从 S 到 F 至少有一条路线。

对于输入文件中的每个测试用例，输出应该在一行上包含一个数字：最小长度或更长一个距离单位的路由数量。这个数字最多为 10^9=1000000000。

算法竞赛进阶指南