모비스터디

현대모비스는 글로벌 자동차 부품 기업으로 자율주행, 커넥티비티, 전동화 분야에 역량을 집중해 스마트 모빌리티 시대를 선도하고 있습니다.

현대모비스는 앞으로 미래 모빌리티 산업에서 소프트웨어와 하드웨어를 결합한 차별화된 모빌리티 솔루션을 제공하는 선도기업으로 도약하기 위해 노력하고 있으며, 이러한 연구개발과 생산능력 등 핵심역량을 바탕으로 스마트 모빌리티, UAM, 로보틱스 사업분야로 비즈니스를 확대해 나가고 있습니다.

민겸이와 시은이는 이런 꿈의 직장인 현대모비스에 입사하기 위해 모비스터디라는 이름의 스터디를 진행하기로 했다. 하지만, 민겸이와 시은이는 서로 다른 도시에 살고 있기 때문에, 스터디를 진행할 장소를 정해야 한다.

민겸이와 시은이는 $1$번부터 $N$번까지 번호가 부여된 $N$개의 도시와 서로 다른 두 도시를 잇는 $M$개의 양방향 도로가 있는 나라에 살고 있다. 도로마다 통행하는 데 걸리는 시간이 양의 정수로 존재하고, 각 도시에서 도로를 통해 항상 다른 모든 도시로 이동할 수 있다. 또한, 같은 도시를 출발지와 도착지로 두고 있는 도로는 존재하지 않으며, 임의의 두 도시를 잇는 도로는 최대 1개 존재한다.

민겸이는 $A$번 도시, 시은이는 $B$번 도시에 살고 있다. 민겸이는 시은이와 모비스터디를 위해 둘이서 만날 도시를 정하려고 한다. 최단 경로 문제를 풀던 민겸이는 약속 장소를 정할 때, $A$ 도시에서 $B$ 도시까지 이동하는 최단 경로 위에 존재하는 도시로 약속 장소를 정하는 것이 좋다고 생각했다. 이때, 최단 경로가 여러 개라면 그중 하나 위에만 존재해도 된다. $A$번 도시와 $B$번 도시 또한 약속 장소가 될 수 있음에 유의하자.

하지만, 민겸이는 이러한 조건을 만족하는 도시가 어디 있는지 모른다. 민겸이는 이 문제를 풀기에는 너무 귀찮았기 때문에, 여러분에게 해결을 부탁했다.

첫 번째 줄에 도시의 개수 $N$과 도로의 개수 $M$, 민겸이가 살고 있는 도시의 번호 $A$, 시은이가 살고 있는 도시의 번호 $B$가 공백으로 구분되어 주어진다. $(2 \le N \le 200\\,000; 1 \le M \le 300\\,000; 1 \le A, B \le N; A \ne B)$

다음 $M$개에 줄에 각 도로의 정보를 나타내는 세 정수 $a$, $b$, $c$가 공백으로 구분되어 주어진다. 해당 도로는 $a$ 도시와 $b$ 도시를 양방향으로 잇고 있으며, 통행하는 데 $c$만큼의 시간이 걸린다. $(1 \le a, b \le N; 1 \le c \le 10^9; a \ne b)$

입력으로 주어지는 모든 수는 양의 정수다.

첫째 줄에 민겸이가 약속 장소로 정할 수 있는 도시의 개수를 출력한다.

둘째 줄에 민겸이가 약속 장소로 정할 수 있는 도시의 번호를 공백으로 구분하여 오름차순으로 출력한다.