T420157 「YAC Round 2」妖梦的麻薯之行

 > 春天是破晓的时候最好。渐渐发白的山顶，有点亮了起来，紫色的云彩微细地飘横在那里。

幽幽子是冥界白玉楼的主人，掌管着冥界的幽灵，但是身为白玉楼主人的她却非常喜欢吃麻薯。妖梦是幽幽子现在身边的庭师兼护卫，为了幽幽子大人每天能够吃到麻薯~~并且防止自己的半灵被幽幽子看成是麻薯而被吞掉~~，妖梦需要从白玉楼到人间之里去购买麻薯。 在幻想乡中，共有 $N$ 个地点和 $M$ 条 **单向道路**，白玉楼的代表 $1$ 号点，人间之里代表 $N$ 号点。也就是说，妖梦需要从 $1$ 号地点（白玉楼）走到 $N$ 号地点人间之里购买真正的麻薯。 通常情况下，$1$ 号地点到 $N$ 号地点的最短路径是妖梦前往人间之里购买麻薯的最佳选择，毕竟路途长度最短嘛。但是，最短路径上的道路可能会出现一些突发状况，比如发生异变啥的，也有可能麻薯会被沿途的某只永远亭的小兔子给忽悠去了，又有可能被某位金发小女孩给偷走之类的。因为这些突发状况不知道何时发生，妖梦需要一些备用的路线方案。不过，这些路线方案也不能消耗她太多时间，不然家里的幽幽子又要饿坏了。 假设 $1$ 号地点到 $N$ 号地点的一条最短路长度为 $dist$，在 $1$ 号地点到 $N$ 号地点往往还会存在比 $dist$ 长一些的路线（当然也有可能存在一些路线长度和最短路长度 $dist$ 相同）。妖梦可以接受的是路线长度 **小于等于** $dist + K$ 的路线。 现在，妖梦需要知道有多少种可以从白玉楼到人间之里买麻薯的满足条件的路线方案。如果存在无穷个满足条件的路线方案，则输出 $-1$；否则输出满足条件的路线的数量。 方案数可能很大，需要对 $P$ 取模运算。

**有多组测试数据** 第一行包含一个整数 $T$, 代表测试数据组数。 接下来 $T$ 组数据。 对于每组数据，第一行包含四个整数 $N,M,K,P$。$N$ 表示地点个数，$M$ 表示道路个数，$K$ 为题中条件，$P$ 为取模运算的数。 接下来 $M$ 行，每行三个整数 $u_i,v_i,w_i$，代表编号为 $u_i,v_i$ 的地点之间有一条长度为 $w_i$ 的单向道路（有向边）。

输出包含 $T$ 行，每行一个整数代表满足条件的路线数量。 注意如果存在无穷个满足条件的路线方案，则输出 $-1$。

#### 样例解释1 对于第一组数据，最短路为 $3$。 $1\to 2\to 4\to 5，1\to 5， 1\to 2\to 3\to 5$ 为 $3$ 条合法路线。 #### 数据范围 对于每个数据点，数据规模不会超过如下表格 测试点编号　　|$T$　　　|$N$　　　|$M$　　　|$K$　　　|是否有 $0$ 边 -|-|-|-|-|- $1$|$5$|$5$|$10$|$0$|否 $2$|$5$|$10^3$|$2\times 10^3$|$0$|否 $3$|$5$|$10^3$|$2\times 10^3$|$50$|否 $4$|$5$|$10^3$|$2\times 10^3$|$50$|否 $5$|$5$|$10^3$|$2\times 10^3$|$50$|否 $6$|$5$|$10^3$|$2\times 10^3$|$50$|是 $7$|$5$|$10^5$|$2\times 10^5$|$0$|否 $8$|$3$|$10^5$|$2\times 10^5$|$50$|否 $9$|$3$|$10^5$|$2\times 10^5$|$50$|是 $10$|$3$|$10^5$|$2\times 10^5$|$50$|是 对于所有数据，$1 \le P \le 10^9$，$1 \le u_i,v_i \le N$，$0 \le w_i \le 1000$。 数据保证至少有一条合法的路线。 #### 提示 数据量较大，你可能需要采用速度比较快的输入输出方式，并且开启 O2 优化（luogu测评机有开启 O2 优化的选项）。