1005: [중급134p] R&E가는길 (Tiny)_1
메모리제한：256 MB
시간제한：1.000 S
체점 스타일：텍스트 비교
만든사람：
제출：0
통과：0
문제 설명
현호가 GSHS에서 R&E 교수님을 뵈러 S대학교를 가려고 한다.
경유하는 지역(GSHS와 S대학교 포함)이 n개, 한 지역에서 다른 지역으로 가는 방법이 총 m개이며 GSHS는 지역 1이고 S대학교는 지역 n이라고 할 때 현호가 S대학교로 가는데 드는 최소 비용을 구하시오.
단, n은 10 이하, m은 30 이하, 그리고 한 지역에서 다른 지역으로 가는 데에 필요한 비용은 모두 200이하 양의 정수이며 한 지역에서 다른 지역으로 가는 어떠한 방법이 존재하면 같은 방법과 비용을 통해 역방향으로 갈 수 있다.
다음 그래프는 예를 보여준다.(단, 정점a->정점b로의 간선이 여러 개 있을 수 있으며, 자기 자신으로 가는 정점을 가질 수도 있다.)
최소 비용이 드는 경로 : 1→3→5→7
최소 비용 : 69+59+21=149
경유하는 지역(GSHS와 S대학교 포함)이 n개, 한 지역에서 다른 지역으로 가는 방법이 총 m개이며 GSHS는 지역 1이고 S대학교는 지역 n이라고 할 때 현호가 S대학교로 가는데 드는 최소 비용을 구하시오.
단, n은 10 이하, m은 30 이하, 그리고 한 지역에서 다른 지역으로 가는 데에 필요한 비용은 모두 200이하 양의 정수이며 한 지역에서 다른 지역으로 가는 어떠한 방법이 존재하면 같은 방법과 비용을 통해 역방향으로 갈 수 있다.
다음 그래프는 예를 보여준다.(단, 정점a->정점b로의 간선이 여러 개 있을 수 있으며, 자기 자신으로 가는 정점을 가질 수도 있다.)
최소 비용이 드는 경로 : 1→3→5→7
최소 비용 : 69+59+21=149
입력 설명
첫째 줄에는 한 칸씩의 공백을 두어 지역의 수와 한 지역에서 다른 지역으로 가는 총 방법의 수가 주어지며 두 번째 줄부터 m+1줄까지는 한 칸씩의 공백을 두어 각 지역과 그 지역에서 갈 수 있는 지역 그리고 그 지역으로 가는데 필요한 비용이 주어진다.
출력 설명
첫째 줄에 S대학교를 가는데 드는 최소 비용을 출력한다. 만약 현호가 S대학교를 갈 수 없다면 -1을 첫째 줄에 출력한다.(단, 큰따옴표는 출력하지 않는다)
입력 예시 복사
<br/>7 11<br/>1 2 47<br/>1 3 69<br/>2 4 57<br/>2 5 124<br/>3 4 37<br/>3 5 59<br/>3 6 86<br/>4 6 27<br/>4 7 94<br/>5 7 21<br/>6 7 40<br/><br/>출력 예시 복사
<br/>149
<br/><br/><center>
<b><font color="#800000" size="3">