AT_code_festival_morning_easy_c 身体バランス

C さん非常喜欢使用斜挎包。然而，如果总是把包挂在同一侧的肩膀上，身体会变得不平衡，因此他决定尽量让包在左右肩膀上挂的时间相同。 C さん所在的国家有 $n$ 个城市，以及连接这些城市的 $m$ 条道路。任意两条不同的道路所连接的城市对都不会相同。 有一天，C さん需要从城市 $s$ 前往城市 $t$。他希望在途中某个城市 $u$ 只换一次肩膀，从而保证包在左右肩膀上挂的时间相同。不过，C さん非常强大且追求速度，因此他从城市 $s$ 到城市 $u$，以及从城市 $u$ 到城市 $t$，都必须选择最短路径。 请你判断是否存在这样的城市 $u$，使得从 $s$ 到 $u$ 的最短路径时间与从 $u$ 到 $t$ 的最短路径时间相等。如果存在，输出任意一个满足条件的城市编号 $u$；如果不存在，输出 $-1$。

输入如下所示： > $n$ $m$ > $s$ $t$ > $x_1$ $y_1$ $d_1$ > $x_2$ $y_2$ $d_2$ > $\vdots$ > $x_m$ $y_m$ $d_m$ - 第 $1$ 行包含两个整数 $n$（城市数，$3 \leq n \leq 1000$）和 $m$（道路数，$1 \leq m \leq \min(n(n-1)/2, 10^4)$）。 - 城市编号为 $1$ 到 $n$。 - 第 $2$ 行包含两个整数 $s$（出发城市编号，$1 \leq s \leq n$）和 $t$（目的地城市编号，$1 \leq t \leq n$）。 - 接下来 $m$ 行，每行包含三个整数 $x_i, y_i$（$1 \leq x_i, y_i \leq n$ 且 $x_i \neq y_i$）和 $d_i$（$1 \leq d_i \leq 1000$），表示第 $i$ 条道路连接城市 $x_i$ 和 $y_i$，通过该道路需要 $d_i$ 的时间。 - 保证从城市 $s$ 可以到达城市 $t$。

如果存在满足条件的城市 $u$，输出该城市编号（任意一个即可），否则输出 $-1$。 输出需换行，且不得输出多余的字符或空行。

### 样例解释 1 如果从城市 $1$ 前往城市 $2$ 时经过城市 $3$，则 $1 \to 3$ 需要 $3$ 的时间，$3 \to 2$ 也需要 $3$ 的时间，因此可以在城市 $3$ 换肩膀，从而左右肩膀负担相同。 ### 样例解释 2 虽然可以通过 $1 \to 2 \to 4 \to 3$ 的顺序，在城市 $4$ 换肩膀使左右负担相同，但 C さん必须从 $1$ 到 $4$ 选择最短路径，因此不能这样移动。 由 ChatGPT 4.1 翻译