최소 비용 경로 구하기

도시가 $n$개 있고, 한 도시에서 출발해 다른 도시에 도착하는 버스가 $m$개 있다. $A$번 도시에서 $B$번 도시까지 가는 데 드는 버스 비용의 합을 최소로 만들려고 한다. 그 최소 비용과 최소 비용을 갖는 경로를 출력한다. 시작 도시에서 도착 도시로 가는 경로는 항상 존재한다.

최소 비용을 갖는 경로가 여러 개면 다음 순서로 하나를 고른다.

1. 지나는 도시의 개수가 가장 적은 경로를 고른다.
2. 그런 경로가 여러 개면, 방문 순서대로 나열한 도시 번호의 수열이 사전순으로 가장 앞서는 경로를 고른다.

첫째 줄에 도시의 개수 $n$이 주어진다. $1 \le n \le 1000$

둘째 줄에 버스의 개수 $m$이 주어진다. $1 \le m \le 100000$

셋째 줄부터 $m$개의 줄에 버스 정보가 출발 도시의 번호, 도착 도시의 번호, 비용 순서로 주어진다. 비용은 $0$ 이상 $100000$ 미만의 정수다. 출발 도시와 도착 도시가 같은 버스는 없고, 같은 구간을 오가는 버스가 여러 개 있을 수 있다.

마지막 줄에 구하려는 구간의 출발 도시 번호 $A$와 도착 도시 번호 $B$가 주어진다. $A$와 $B$는 서로 다르다.

첫째 줄에 $A$에서 $B$까지 가는 데 드는 최소 비용을 출력한다.

둘째 줄에 고른 경로에 포함된 도시의 개수를 출력한다. 출발 도시와 도착 도시도 센다.

셋째 줄에 고른 경로가 지나는 도시의 번호를 방문 순서대로 공백으로 구분해 출력한다. 두 가지 우선순위를 모두 만족하는 경로는 하나뿐이다.