Лабиринт

Лабиринт --- это сооружение, которое состоит из комнат и магических порталов. Каждый портал соединяет две комнаты. Портал выглядит как обычная дверь, но если эту дверь открыть, то мгновенно переносишься в ту комнату, в которую портал ведет.

На двери каждого портала со стороны комнаты написано некоторое слово. Истинное назначение этих пометок на дверях никому не известно. Некоторые исследователи считают, что их можно исследовать для ориентирования в лабиринте. Другие думают, что смысл имеют не отдельные слова, написанные на дверях, а последовательности букв, которые получаются, если записать друг за другом несколько слов, которые написаны на дверях порталов, проходимых на пути из одной комнаты в другую. Такие последовательности букв в дальнейшем будем называть метками путей. Один из исследователей полагает, что важны метки не всех путей из одной комнаты в другую, а только наиболее короткие из них.

Ваша задача состоит в том, чтобы написать программу, которая по описанию лабиринта и номерам начальной и конечной комнат пути найдет самую короткую метку пути между этими комнатами. Если существует несколько самых коротких меток пути, то необходимо найти лексикографически наименьшую среди них.

Первая строка входного файла содержит два целых числа: $n$ и $m$ ($2 \le n \le 2000$, $1 \le m \le 50000$). Каждая из последующих $m$ строк описывает один портал и содержит два числа: $u$ и $v$ ($1 \le u, v \le n$, $u \ne v$) --- соответственно, номер комнаты, из которой портал выходит, и номер комнаты, в которую портал ведет, и слово $w$ --- пометку на двери портала, соединяющего эти комнаты (длина $w$ находится в пределах от одного до десяти символов, $w$ содержит только строчные буквы латинского алфавита).

Последняя строка входного файла содержит два целых числа: $s$ и $t$ ($1 \le s, t \le n$, $s \ne t$) --- номера начальной и конечной комнаты пути, соответственно.

Если из комнаты $s$ нельзя добраться до комнаты $t$, то выведите в выходной файл слово Impossible. Иначе, выведите в выходной файл искомую метку пути.