MST

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

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

세빈이는 이 그래프에 다음 쿼리를 $M$번 수행했다.

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

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

첫째 줄에 $N$과 $M$이 공백을 사이에 두고 주어진다. ($2 \le N \le 200000$; $0 \le M \le 200000$)

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

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

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

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

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