빠른 알고리즘

Little I는 유향 그래프에서 최소 사이클을 $O(n + m)$ 시간에 찾는 알고리즘을 고안했다. 이제 그는 여러분의 실력을 시험하려 한다.

정점 $n$개와 간선 $m$개로 이루어진 유향 그래프가 주어진다. 각 간선에는 양의 정수 가중치가 있다. 간선 가중치의 합이 최소가 되는 사이클을 찾아, 그 합의 최솟값을 출력하라. 사이클이 없으면 그 사실을 보고하라.

$O(n + m)$ 알고리즘을 모를 수 있으므로, Little I는 조건을 완화했다. 입력 그래프는 약한 연결 그래프임이 보장되고, $m - n$은 그리 크지 않다. 방향 간선을 모두 무방향 간선으로 바꿨을 때 연결된 무방향 그래프가 되면 약한 연결 그래프이다.

첫째 줄에 정점의 수 $n$과 간선의 수 $m$이 주어진다 ($1 \le n \le 3 \cdot 10^5$, $-1 \le m - n \le 1500$).

이어지는 $m$개의 줄에는 정수 $u_i$, $v_i$, $w_i$가 주어진다 ($1 \le u_i, v_i \le n$, $1 \le w_i \le 10^9$). 이는 정점 $u_i$에서 $v_i$로 향하고 가중치가 $w_i$인 간선을 뜻한다. 그래프는 약한 연결 그래프이다.

최소 사이클의 길이를 한 줄에 출력한다. 사이클이 없으면 $-1$을 출력한다.

첫 번째 예제에서 최소 사이클은 $1 \to 2 \to 4 \to 3 \to 1$이다.