문제
지방에서 서울에 관광온 도훈이는 지하철 노선을 보고 깜짝 놀랐다.
노선이 엄청나게 복잡하기 때문이었다.
각 노선들이 서로 얽혀있어서 잘못하면 10분도 안걸리는 거리를 1시간 동안 갈 수도 있는 상황이었다.
어쩔 수 없이 도훈이는 현재 숙소에서 관광할 목적지까지 가장 짧은 시간에 도착할 수 있는 경로와 시간을 표로 만들려고 한다.
단, 각 지하철역에서 관광지가 있고, 지하철을 갈아타는데 소요되는 시간은 없다고 가정한다.
입력
첫줄에 N(3≤N≤100), M(1≤M≤N)을 입력 받는다.
N은 지하철역의 수, M은 원하는 목적역의 번호를 입력받는다.
둘째 줄부터 N개의 줄이 나오고, 각 줄에는 N개의 수 S가 입력된다.
i번째 줄에서 j번째 수 Sij는 i번역에서 j번 역까지 가는데 걸리는 시간이다.
1번 역이 숙소가 있는 역이고, Sij에서 i = j 일 때는 항상 0 이다. (0≤S≤100)
출력
목적 역까지 가는데 걸리는 최소 시간과 최소시간으로 가는 최단경로를 출력한다.
예제1
입력
55
02259
20348
23076
54705
95650
출력
8
135
힌트