왕복 최단 거리

첫 줄에 노드의 수 n (2 이상 100000 이하) 과 간선의 수 m (0 이상 4000 이하) 이 주어집니다. 이어서 m개의 줄에 방향 간선 u v w 가 주어집니다. 비용 w 는 1 이상 1000000 이하입니다.

1번에서 n번까지 갔다가 다시 1번으로 돌아오는 최단 거리를 출력하세요. 방향 간선이라 가는 길과 오는 길이 다를 수 있습니다. 왕복이 불가능하면 -1 을 출력합니다.

예시

입력

4 6
1 2 1
2 4 2
4 3 1
3 1 2
1 4 10
4 1 10

출력

6