Olympic Avenues

At the Athens 2004 Olympic Games there were many Olympic sites (stadiums, the Olympic Village, the Press Center, offices, and so on). So that athletes, officials, and journalists could move quickly between the sites, Athens built roads called "Olympic Avenues" on which only Olympic buses were allowed. Each Olympic avenue directly connects exactly two Olympic sites. Not every pair of sites is directly connected, and a single avenue joins exactly two sites. A bus driver wants to travel from one Olympic site to another using only Olympic avenues. Given the information about the sites and the avenues, find a shortest route between two sites that uses only Olympic avenues. An avenue can be traveled in either direction.

The first line contains one integer $N$, the number of Olympic sites ($5 \le N \le 50$). The second line contains two integers $S$ and $F$: the numbers of the starting and ending sites of the route. The third line contains one integer $L$, the number of Olympic avenues. Each of the following $L$ lines contains three integers $I$, $J$, and $D$: the two sites $I$ and $J$ connected by the avenue and the distance $D$ between them ($D$ is a positive integer). Sites are numbered from 1 to $N$. The input has the following form.

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

On the first line, print the length (total distance) of the shortest route from $S$ to $F$. On the second line, print the numbers of the sites visited along that route in order, with $S$ first and $F$ last. If several shortest routes exist, print the one whose sequence of site numbers is lexicographically smallest (compare the two sequences element by element from the front; the sequence with the smaller element comes first). If $S$ and $F$ are the same site, the length is 0 and the second line contains only $S$.