题目描述

c先生非常喜欢背斜挎包出去办事。 但是如果只把包挎在一边的肩膀上的话，据说身体会变歪的，这对于c先生这种强最快的男人来说的话，无异于受到屈辱，所以在两边的肩膀上只能在同样的时间里背挎包（注意！！！）。

c先生住的国家有n个城市和连接城市之间的m条路。 无论哪两条不同的路，连接的2个城市都不会是一样的。

c先生有一天需要从城市s到城市t去办事。 c先生想在中途的城市u只换一次包，把包挂在左右肩膀上的时间相同。 但是，c先生是他住的国家里最强最快的男人（男人不能说自己不行）， 所以c先生需要走从城市s到城市u再从城市u到城市t的最短路径。

请你帮帮c先生找一找有没有这种城市u的选择方法呢。 输入格式

输入以以下形式给出。

 $ n $   $ m $ 
 $ s $   $ t $ 
 $ x_1 $   $ y_1 $   $ d_1 $ 
 $ x_2 $   $ y_2 $   $ d_2 $ 
 $ ... $ 
 $ x_m $   $ y_m $   $ d_m $ 

• 第一行是表示城市数量的整数n ( 3 ≤ n ≤ 1,000 )和表示道路数量的整数m( 1 ≤ m ≤ min(n(n−1)/2, 10 ^4) )

• 城市编号为1到n。

• 第二行是表示出发城市编号的整数s( 1 ≤ s ≤ n ) 和表示目的地城市编号的t( 1 ≤ t ≤ n )。