문제

참가자의 편의를 위해, 지문을 최대한 간단하게 작성했다.

간단한 최단 경로는, 간선을 최소한으로 사용하는 경로 중 거리가 가장 짧은 경로를 의미한다.

가중치가 있는 방향그래프와 시작점, 끝점이 주어질 때, 시작점에서 끝점으로 가는 간단한 최단 경로를 구해보자.

입력

첫째 줄에는 정점의 개수 와 간선의 개수 가 주어진다. (, )

둘째 줄부터 개의 줄에 간선의 정보 가 주어진다. 이는 번 정점에서 번 정점으로 가는 길이가 인 간선을 의미한다. (, , )

번째 줄에는 시작점과 끝점 가 주어진다. ()

출력

시작점에서 끝점으로 가는 간단한 최단 경로의 길이를 출력한다.

단, 시작점에서 끝점으로 가는 경로가 존재하지 않으면 -1을 출력한다.