연애 혁명

신촌고등학교 학생회장 기령이는 최근 학생들의 복잡한 사랑 관계 때문에 고민이 많다. 학생들이 공부에 집중하지 못해 전반적인 성적이 떨어지고 있다. 이에 기령이는 학생들의 복잡한 마음을 덜어주기 위해 일부 사랑 관계를 강제로 포기하게 하는 특단의 조치를 취하기로 했다. 단, 파장을 최소화하기 위해 다음 조건을 만족하도록 조치한다. (1) 이미 성사된 사랑 관계는 포기하게 하지 않는다. (2) 사랑 관계가 $K$각 관계를 이루지 않도록 한다. $K$($K \geq 3$)각 관계란 임의의 서로 다른 $K$명의 학생 $A_1, A_2, \cdots, A_K$에 대하여, $i \neq 1$인 모든 $i$에 대해 $A_{i-1}$과 $A_i$ 사이에 사랑 관계가 있고, $A_K$와 $A_1$ 사이에도 사랑 관계가 있는 것을 뜻한다. (3) 포기하게 만들 수 있는 경우가 여러 가지면 포기하게 만든 애정도의 합을 최소화한다. 다만 학생 수가 매우 많아 이 조건을 만족하는 경우를 찾기 어렵다. 조건을 만족하도록 사랑 관계를 포기하게 했을 때, 포기하게 만든 애정도 합의 최솟값을 구해보자.

첫째 줄에 학생 수 $N(3 \leq N \leq 10\ 000)$과 사랑 관계 수 $M(N \leq M \leq 100\ 000)$이 주어진다. 이후 $M$개의 줄에 걸쳐 사랑 관계를 나타내는 정수 $a_i$, $b_i$, $c_i$와 성사 여부 $d_i$가 공백으로 구분되어 주어진다. $(1 \leq a_i < b_i \leq N; 1 \leq c_i \leq 10\ 000)$ 학생 $a_i$와 $b_i$가 애정도 $c_i$인 사랑 관계에 있으며, $d_i$가 1이면 이미 성사된 관계, 0이면 그렇지 않음을 뜻한다. 주어지는 데이터에서 임의의 두 학생은 한 개 이상의 사랑 관계로 연결되어 있고, 같은 두 학생 사이의 사랑 관계는 여러 번 주어지지 않는다. 또한 성사된 사랑 관계만으로 이루어진 $K$각 관계는 존재하지 않는다.

포기하게 만든 애정도 합의 최솟값을 출력한다.