올림픽 대로

2004년 아테네 올림픽에는 경기장, 선수촌, 프레스 센터, 사무실 등 여러 올림픽 시설이 있었다. 선수, 관계자, 기자들이 시설 사이를 빠르게 이동할 수 있도록 아테네는 올림픽 버스만 다닐 수 있는 '올림픽 대로(Olympic Avenue)'를 만들었다. 각 올림픽 대로는 정확히 두 시설을 직접 연결한다. 모든 시설이 대로로 직접 연결되어 있는 것은 아니며, 하나의 대로는 정확히 두 시설을 잇는다. 한 버스 기사가 오직 올림픽 대로만 이용해 어떤 시설에서 다른 시설로 이동하려 한다. 올림픽 시설과 대로에 대한 정보가 주어질 때, 올림픽 대로만 이용해 두 시설 사이를 이동하는 가장 짧은 경로를 구하여라. 대로는 양방향으로 통행할 수 있다.

첫째 줄에 올림픽 시설의 수 $N$이 주어진다 ($5 \le N \le 50$). 둘째 줄에는 두 정수 $S$와 $F$가 주어지며, 각각 경로의 시작 시설과 도착 시설의 번호이다. 셋째 줄에는 올림픽 대로의 수 $L$이 주어진다. 이어지는 $L$개의 줄에는 각 대로의 정보가 주어진다. 각 줄에는 세 정수 $I$, $J$, $D$가 주어지는데, $I$와 $J$는 대로가 연결하는 두 시설의 번호이고 $D$는 두 시설 사이의 거리이다($D$는 양의 정수). 시설의 번호는 1부터 $N$까지이다. 입력의 형식은 다음과 같다.

N
S F
L
I1 J1 D1
I2 J2 D2
...
IL JL DL

첫째 줄에 $S$에서 $F$까지 가는 가장 짧은 경로의 길이(거리의 합)를 출력한다. 둘째 줄에는 그 경로에서 방문하는 시설들의 번호를 순서대로 출력하며, 첫 번째 수는 $S$, 마지막 수는 $F$이다. 가장 짧은 경로가 여러 개인 경우, 시설 번호의 수열이 사전순으로 가장 앞서는 경로를 출력한다(두 수열을 앞에서부터 원소 단위로 비교했을 때, 더 작은 원소를 갖는 쪽이 사전순으로 앞선다). $S$와 $F$가 같은 시설인 경우, 경로의 길이는 0이고 둘째 줄에는 $S$만 출력한다.