题目描述

给定一个包含 (n) 个点、(m) 条无向边的带权图。请你求从起点 (s) 到终点 (t) 的最短路径共有多少种不同的方案（不同方案指路径经过的点序列不同）。

格式

输入

第一行输入两个整数 (n,m)（(1 \le n \le 100)）。 接下来 (m) 行，每行输入三个整数 (u,v,w)（(1 \le w \le 100)），表示点 (u) 与点 (v) 之间有一条权值为 (w) 的无向边。 最后一行输入两个整数 (s,t)，分别表示起点与终点。

注意：图中可能存在重边；不存在自环。

输出

输出一个整数，表示从 (s) 到 (t) 的最短路径方案数。

样例

4 4
1 2 1
1 3 1
2 4 1
3 4 1
1 4

2