골드는 연구활동 교수님을 뵈러 A대학교를 가려고 한다.

출발점과 도착점을 포함하여 경유하는 지역 \(n\)개, 한 지역에서 다른 지역으로 가는 방법이 총 \(m\)개이며

골드의 위치는 지역 1이고 A대학교는 지역 \(n\)이라고 할 때 대학까지 최소 비용을 구하시오.

입력

첫 번째 줄에는 정점의 수 \(n\)과 간선의 수 \(m\)이 공백으로 구분되어 입력된다.

다음 줄부터 \(m\)줄에 걸쳐서 두 정점의 번호 \(u, v\)와 가중치 \(w\)가 입력된다.

(자기 자신을 가리키는 간선인 자기 간선이나, 같은 정점 쌍 사이에 여러 간선이 존재하는 멀티 간선이 있을 수 있다.)

출력

대학까지 가는데 드는 최소 비용을 출력한다. 만약 갈 수 없다면 -1을 출력한다.

제한사항

• \(2 \le n \le 15\)
• \(1 \le m \le 120\)
• \(1 \le u, v \le n\)
• \(1 \le w \le 1,000\) (\(w\)는 정수)

예제 입력 1

7 11
1 2 47
1 3 69
2 4 57
2 5 124
3 4 37
3 5 59
3 6 86
4 6 27
4 7 94
5 7 21
6 7 40

예제 출력 1

149

예제 입력 2

4 2
1 2 10
2 3 20

예제 출력 2

-1