题目描述

人类和人鱼拥有共同的祖先，因为某种原因发生了分化，人鱼到了大海里生活。近年来人类对大海及生态的破坏，人鱼族的生存环境受到了严重的影响。最近某地产公司筹备一个填海计划，在附近的大海中装入了声呐系统，这极大地限制了人鱼的活动。

人鱼族的居民们为了适应环境，建立了 $n$ 个聚居点（从 $1$ 到 $n$ 编号），$m$ 条有一定长度的单向通道，每条由一个聚居点通向另一个聚居点。人鱼族派出了美人鱼珊珊去勾引地产公司的老总刘轩，来逼迫他关闭声呐系统。现在珊珊在 $S$ 号点，她要到 $T$ 号点，然后通过 $T$ 号点到达陆地上。她当然希望自己能走最短的路来从 $S$ 到达 $T$，不过比最短路长 $1$ 的路径，她也是可以接受的。她想知道从 $S$ 到 $T$ 的最短路和比最短路长 $1$ 的路径一共有多少条。

输入格式

输入数据共 $m+2$ 行。

第一行两个数 $n, m$，含义如题目所述。（$1 \leq n \leq 1000$，$1 \leq m \leq 15000$）

第 $2$ 到 $m+1$ 行，共 $m$ 行，每行 $3$ 个数 $a[i], b[i], c[i]$，表示从 $a[i]$ 到 $b[i]$ 有一条长度为 $c[i]$ 的通道（$1 \leq a[i], b[i] \leq n$，$1 \leq c[i] \leq 10000$，可能有重边）。

第 $m+2$ 行两个数 $S, T$，含义如题目所述。

输出格式

输出一个数，表示从 $S$ 到 $T$ 的最短路和比最短路长 $1$ 的路径的数目。

样例输入

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

样例输出

3