Problem 1003. -- 美人鱼

1003: 美人鱼

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 4631  Solved: 65
[Submit][Status][Web Board]

Description

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

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

Input

输入数据共m+2行。

第一行两个数n,m,含义如题目所述。(1<=n<=10001<=m<=15000

2m+1行,共m行,每行3个数a[i],b[i],c[i],表示从a[i]b[i]有一条长度为c[i]的通道(1<=a[i],b[i]<=n1<=c[i]<=10000,可能有重边)。

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

Output

输出一个数,表示从ST的最短路和比最短路长1的路径的数目。

Sample Input

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

Sample Output

3

HINT

Source

[Submit][Status]