한 실험용 제어판에는 1번부터 V번까지 번호가 붙은 단자가 있다. 단자 사이에는 E개의 단방향 신호관이 설치되어 있으며, 각 신호관을 통과할 때마다 정해진 지연값이 더해진다.

검사 장비는 어떤 단자에서 신호를 내보낸 뒤, 설치된 신호관만 따라가다가 다시 처음 단자로 돌아오는 닫힌 신호 루프를 찾으려고 한다. 루프의 비용은 사용한 신호관들의 지연값 합이다. 서로 다른 두 단자를 오가는 두 개의 신호관을 각각 한 번씩 사용하는 경우도 닫힌 루프로 인정한다.

제어판의 연결 정보가 주어졌을 때, 만들 수 있는 닫힌 신호 루프 중 비용이 가장 작은 값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 단자의 개수 V와 신호관의 개수 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1))

다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. 이는 a번 단자에서 b번 단자로 향하는 지연값 c의 신호관이 있다는 뜻이다. 방향이 있음에 주의한다. 지연값은 10,000 이하의 자연수이다. 같은 (a, b) 쌍의 신호관은 여러 번 주어지지 않는다.

출력

첫째 줄에 닫힌 신호 루프의 최소 비용을 출력한다. 그런 루프를 만들 수 없다면 -1을 출력한다.

예제 입력 1

3 4
1 2 1
3 2 1
1 3 5
2 3 2

예제 출력 1

3