JOI 나라에는 섬이 \(n\)개 있고, 각 섬에는 \(1\)부터 \(n\)까지 번호가 붙어 있다. 지금은 섬을 잇는 배편이 하나씩 열리고 있다. 당신은 배표 안내소에서 일한다. 손님은 출발 섬과 도착 섬을 주문표에 적어 보낸다. 주문표를 받으면 배를 갈아타며 갈 수 있는 가장 싼 운임을 바로 알려 주어야 한다. 어떤 여정은 배로는 갈 수 없고, 그때는 배로는 여행할 수 없다고 알려야 한다. 새 배편이 수시로 운항을 시작하므로 손님에게 답할 때는 그때까지의 정보를 모두 반영해야 한다. 손님의 주문표와 새로 운항을 시작한 배편 정보가 주어질 때, 손님에게 할 답을 구하는 프로그램을 작성하라. 처음에는 운항 중인 배가 한 척도 없다. 같은 섬 사이를 여러 배가 다닐 수 있다. |
입력은 다음 형식으로 주어진다.
\(n\) \(k\)
이어지는 \(k\)줄은 각각 다음 두 형식 중 하나이다.
\(0\) \(a\) \(b\)
\(1\) \(c\) \(d\) \(e\)
- 첫째 줄에 섬의 수 \(n\)과 이어지는 줄 수 \(k\)가 공백 하나로 구분되어 주어진다.
- 다음 \(k\)줄의 첫 수가 \(0\)이면 그 줄은 주문표이다. 정수 \(0\), \(a\), \(b\)가 공백 하나로 구분되어 주어지고, 섬 \(a\)에서 섬 \(b\)로 가려는 손님을 뜻한다.
- 첫 수가 \(1\)이면 그 줄은 새 배편이다. 정수 \(1\), \(c\), \(d\), \(e\)가 공백 하나로 구분되어 주어지고, 섬 \(c\)와 섬 \(d\)를 왕복하는 배가 운항을 시작한다. \(c\)에서 \(d\), \(d\)에서 \(c\)의 운임은 모두 \(e\)이다. 이 줄 이후의 주문표에는 이 배편도 반영해야 한다.
- \(1 \le n \le 100\)
- \(1 \le k \le 5000\)
- \(1 \le a, b \le n\), \(a \ne b\)
- \(1 \le c, d \le n\), \(c \ne d\)
- \(1 \le e \le 1000000\)
- 배편을 나타내는 줄은 \(1000\)줄 이하이다.
- 입력되는 값은 모두 정수이다.
다음 형식으로 출력한다.
주문표를 나타내는 줄의 수를 \(m\)이라 하자. \(m\)줄을 출력한다. \(i\)번째 줄에는 \(i\)번째 주문표에 대한 답을 출력한다. 출발지와 도착지를 배를 갈아타며 여행할 수 있으면 운임 합의 최솟값을, 불가능하면 \(-1\)을 출력한다.
첫 주문표가 올 때는 섬 \(2\)와 \(3\)을 잇는 배가 없어 \(-1\)이다. 그다음 주문표에서는 섬 \(3 \to 1 \to 2\)로 가는 운임 \(10+5=15\)가 최소이다. 마지막 주문표에서는 섬 \(2 \to 1 \to 3\)으로 가는 운임 \(5+7=12\)가 최소이다.