Лабиринт

시간 제한2초메모리 제한1024 MB

요약

레이블이 붙은 방향 그래프에서 s에서 t로 가는 경로의 레이블 중 길이가 가장 짧고 사전순으로 가장 앞서는 것을 찾거나 불가능을 판정한다.

난이도: 보통10점 중 7점
유형: 그래프, BFS, 최단 경로, 그리디
정답자: 아직 제출이 없습니다

문제

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

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

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

입력

Первая строка входного файла содержит два целых числа: $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. Иначе, выведите в выходной файл искомую метку пути.

예제3

예제 1

입력

2 3
1 2 alpha
2 1 delta
1 2 gamma
1 2

예상 출력

alpha

예제 2
입력
```
2 2
1 2 alice
1 2 bob
1 2
```
예상 출력
```
bob
```
예제 3
입력
```
2 2
1 2 vice
1 2 versa
2 1
```
예상 출력
```
Impossible
```