N개의 정점과 M개의 방향성 간선으로 이루어진 그래프가 주어집니다. 각 간선은 u번 정점에서 v번 정점으로 향하며, 그 가중치는 w입니다.

시작 정점 A와 도착 정점 B가 주어졌을 때, A에서 B로 가는 최단 경로의 비용과 그 경로를 이루는 정점들을 순서대로 출력하는 프로그램을 작성하시오.

최단 경로가 여러 개 존재할 경우, 그중 어떤 경로를 출력해도 정답으로 인정됩니다.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 공백을 사이에 두고 주어진다.

둘째 줄에는 시작 정점 A와 도착 정점 B가 공백을 사이에 두고 주어진다.

셋째 줄부터 M개의 줄에 걸쳐 각 간선의 정보인 세 정수 u, v, w가 공백을 사이에 두고 주어진다. 이는 u번 정점에서 v번 정점으로 향하는 가중치가 w인 방향성 간선이 존재함을 의미한다.

출력

첫째 줄에 시작 정점 A에서 도착 정점 B로 가는 최단 경로의 비용을 출력한다. (도착할 수 없는 경우 INF를 출력한다.)

둘째 줄에는 최단 경로를 거치는 정점의 개수 K를 출력한다.

셋째 줄에는 최단 경로를 구성하는 K개의 정점을 시작 정점부터 도착 정점까지 순서대로 공백으로 구분하여 출력한다.

(도착할 수 없는 경우 둘째 줄과 셋째 줄은 출력하지 않는다.)

제한 사항

• 1 ≤ N ≤ 100,000
• 0 ≤ M ≤ 200,000
• 1 ≤ A, B ≤ N (A ≠ B)
• 1 ≤ u, v ≤ N
• 1 ≤ w ≤ 10,000 (w는 정수)
• 동일한 시작점과 도착점을 갖는 간선이 여러 개 존재할 수 있습니다. (중복 간선 허용)

예제 입력 1

5 7
1 5
1 2 2
1 3 2
2 4 3
3 4 3
4 5 1
1 5 10
2 5 5

예제 출력 1

6
4
1 2 4 5

예제 입력 2

3 2
1 3
1 2 1
2 3 2

예제 출력 2

3
3
1 2 3