문제

구름이는 이상한 미로에 갇혔다. 미로는 개의 방과 개의 복도로 이루어져 있고, 각 방에는 부터 까지의 번호가 붙어 있다. 그리고 각 방의 바닥에는 부터  사이의 정수 가 쓰여있다.

이 이상한 미로에는 이상한 규칙들이 있다.

• 방에서 움직이는 데 걸리는 시간은 고려하지 않는다.
• 미로에 있는 모든 복도는 양방향으로 이동할 수 있고, 복도마다 지나가는 데 걸리는 시간이 정해져 있다.
• 번 방과 번 방이 복도로 직접 연결되어 있고, 번 방과 번 방이 복도로 직접 연결되어 있을 때, 두 복도를 이용해 번 방에서 번 방으로 이동하려면 를 로 나눈 나머지와 를 로 나눈 나머지가 같아야 한다.

구름이는 현재 번 방에 있고, 탈출구는 번 방에 있다. 구름이가 이 이상한 미로에서 탈출할 수 있는지, 탈출할 수 있다면 구름이가 탈출하기까지 최소 얼마나 시간이 걸리는지 구해보자. 단, 맨 처음에 이용하는 복도는 위의 조건과는 상관 없이 원하는 복도를 이용할 수 있다.

예제 설명

첫 번째 예시에 나온 미로를 그림으로 나타내면 아래와 같다. 파란색 숫자는 그 복도를 지나는 데 걸리는 시간을 의미하고, 빨간색 숫자는 그 방에 바닥에 쓰여있는 정수 를 의미한다.

우선, 1번 방에서 처음 출발할 때는  1 → 3  복도나  1 → 2  복도 중 아무 복도나 이용할 수 있다. 그러나  1 → 2 → 4  와 같이 이동하는 것은 불가능한데, 왜냐하면 1을 로 나눈 나머지와 4를 로 나눈 나머지가 1과 0으로 서로 다르기 때문이다.

위의 미로 형태에서 조건을 만족하는 최단 경로는  1 → 2 → 3 → 4  이고, 이때 걸리는 시간은 15이다. 

두 번째 예시에 나온 미로를 그림으로 나타내면 아래와 같다.

 1 → 2 → 3  과 같이 이동하는 것은 불가능하다. 1과 3을 각각 로 나눈 나머지가 1과 3으로 서로 다르기 때문이다. 따라서 위의 미로에서는 1번 방에서 3번 방에 도달하는 것이 불가능하고, -1을 출력해야 한다.

입력

첫째 줄에는 이상한 미로에 있는 방의 개수 과 복도의 개수 이 공백을 두고 주어진다.
둘째 줄에는 이 공백을 두고 주어진다.
다음 개의 줄에는 복도의 정보를 의미하는 가 공백을 두고 주어진다. 복도는 번 방과 번 방 사이를 잇고 있으며, 복도를 지나는 데 걸리는 시간이 라는 의미이다.

• 
• 
• 
• 
• 
• 입력에서 주어지는 모든 수는 정수이다.
  

출력

구름이가 어떤 경로를 이용하더라도 번 방에 도달할 수 없다면 -1을 출력한다.
그렇지 않다면 번 방에 도달하는 데 필요한 최소 시간을 출력한다.