Первая строка входных данных содержит два целых числа $n$, $m$ ($3 \le n \le 500$, $n - 1 \le m \le \frac{n \cdot (n - 1)}{2}$)~--- количество городов в Берляндии и количество дорог между ними.

В следующих $m$ строках находится по три целых положительных числа $u$, $v$, $c$ ($1 \le u, v \le n$, $u \neq v$, $1 \le c \le 10^5$)~--- пара городов, соединенных дорогой и длина этой дороги.

В последней строке входных данных находятся два целых числа $a$, $b$ ($1 \le a, b \le n$, $a \neq b$)~--- города, в которых находятся столицы первого и второго княжества.
