문제

기숙사에서 일어나 제1공학관을 거쳐 자연과학관에서 수업을 듣고 다시 IT.BT관으로 수업을 들으러 가는 태우는, "학교에 케이블카가 있었으면..." 하는 상상을 하며, 오늘도 등산과 하산을 반복하고 있다.

어느 날 태우의 꿈에, 여러 섬이 케이블카로 연결된 멋진 한양대 캠퍼스가 나타났다!

꿈 속 캠퍼스에는 개의 섬과 이들을 잇는 개의 케이블카가 있다. 번 케이블카는 번 섬과 번 섬을 양방향으로 연결하며, 이동하는 데에는 분이 걸린다.

케이블카는 정해진 시간에만 출발한다. 번 케이블카는 분에 첫 운행을 시작하며, 그 후 분 간격으로 계속 운행한다. 예시로, 가 이라면 분, 분, 분, 분, 에 번 섬과 번 섬에서 출발한다.

어떤 섬에 도착하면, 타려는 케이블카의 다음 출발 시간까지 기다려야 한다. 만약 섬에 도착한 시간과 케이블카의 출발 시간이 정확히 일치한다면, 기다릴 필요 없이 바로 탑승할 수 있다.

꿈 속 한양대의 번 섬에서 번 섬까지 가는 최단 시간을 구해 보자!

입력

첫째 줄에 섬의 수 과 케이블카의 수 가 공백으로 구분되어 주어진다. (; )

이후 개의 줄에 걸쳐 한 줄마다 케이블카의 정보 가 공백으로 구분되어 주어진다. (; ; )

마지막 줄에는 태우의 출발지 와 도착지 가 공백으로 구분되어 주어진다. (; )

두 섬을 연결하는 케이블카의 수는 개 또는 개이며, 모든 쌍에 대해 이동이 가능한 경우만 입력으로 주어진다.

출력

번 섬에서 번 섬까지 이동하는 최단 시간을 출력한다.