25609번 - MST

세빈이에게는 두 가지 취미가 있다. 하나는 디스크립션을 짧게 쓰는 것이고, 다른 하나는 복잡한 그래프에서 최소 스패닝 트리를 구하는 것이다.

N개의 정점으로 이루어진 그래프가 있다. 그래프의 정점에는 0부터 (N − 1)까지의 서로 다른 정수가 번호로 붙어 있다.

세빈이는 그래프에서 다음 쿼리를 M번 수행하였다.

• u v c k : 모든 0 ≤ i < k에 대해 (u + i) mod N번 정점과 (v + i) mod N번 정점 사이 가중치 (c + i)인 간선을 추가한다.

이 그래프의 최소 스패닝 트리의 가중치를 구하여라. 만약 최소 스패닝 트리가 존재하지 않는다면 -1을 출력하여라.

첫째 줄에 N과 M이 공백을 사이에 두고 주어진다. (2 ≤ N ≤ 200 000; 0 ≤ M ≤ 200 000)

둘째 줄부터 M개의 줄에 걸쳐 네 정수 u, v, c, k가 공백을 사이에 두고 주어진다. (0 ≤ u, v < N; 0 ≤ c ≤ 10⁹; 1 ≤ k ≤ N; u ≠ v)

첫째 줄에 최소 스패닝 트리의 가중치를 구하여라. 만약 최소 스패닝 트리가 존재하지 않는다면 -1을 출력하여라.

첫 번째 예제에서, 주어진 그래프와 그래프의 최소 스패닝 트리는 다음과 같다.

그래프의 모든 정점들을 포함하는 연결된 부분 그래프 중에서 간선의 가중치의 합이 최소인 것을 최소 스패닝 트리라고 한다.

최소 스패닝 트리의 가중치란 최소 스패닝 트리에 포함되는 간선의 가중치의 합을 의미한다.