问题描述

C先生很喜欢斜挎包。
然而，由于被告知只在一侧肩上挂包会导致身体歪斜，所以他决定尽量让两侧肩膀上的包挂同样的时间。

C先生所居住的国家有$n$个城市和$m$条连接城市的道路。
对于任意两条不同的道路，连接的两个城市都不相同。

有一天，C先生需要从城市$s$移动到城市$t$。
因此，他希望在途中的城市$u$处只更换一次包，并使得左右肩上挂包的时间相同。
然而，C先生非常强大且快速，从城市$s$到城市$u$，从城市$u$到城市$t$的移动将走最短路径。

请找出是否存在这样的选择城市$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 \leq n \leq 1{,}000$)和$m$ ($1 \leq m \leq min(n(n-1)/2, 10^4)$)，分别表示城市数和道路数。
• 每个城市都被分配了从$1$到$n$的编号。
• 第二行包含两个整数$s$ ($1 \leq s \leq n$)和$t$ ($1 \leq t \leq n$)，表示出发城市和目的地城市。
• 接下来的$m$行给出每条道路的信息。
• 对于第$i$条道路，$x_i, y_i$ ($1 \leq x_i, y_i \leq n$且$x_i \neq y_i$)和$d_i$ ($1 \leq d_i \leq 1{,}000$)表示通过第$i$条道路从城市$x_i$到城市$y_i$需要$d_i$的时间。
• 保证可以从城市$s$到达城市$t$。

输出

如果存在满足条件的城市$u$，则输出该城市的编号。如果存在多个答案，可以输出任意一个。

如果不存在这样的城市$u$，则输出-1。

最后换行，不要有额外的字符或空行。

示例1

3 3
1 2
1 3 3
3 2 3
1 2 1

输出示例1

3

当从城市1移动到城市2时，经过城市3，需要3的时间，然后从城市3移动到城市2，同样需要3的时间，因此只需要经过城市3并在那里更换包即可。

示例2

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

输出示例2

-1

按照$1 \to 2 \to 4 \to 3$的顺序移动，可以通过在城市4更换包来使左右肩承担的负担相同，但C先生会选择从城市1到城市4的最短路径，因此无法进行此类移动。