Love Revolution

Kiryeong, the student council president of Sinchon High School, has been worried about the tangled romances among students lately. Students cannot focus on their studies, so overall grades are falling. To ease their troubled minds, Kiryeong decided to take drastic action and force some of the romantic relationships to be given up. To minimize the fallout, the action must satisfy the following conditions: (1) A relationship that has already been established is not to be given up. (2) The romantic relationships must not form a $K$-gon. A $K$-gon ($K \geq 3$) means that for any $K$ distinct students $A_1, A_2, \cdots, A_K$, there is a romantic relationship between $A_{i-1}$ and $A_i$ for every $i \neq 1$, and also between $A_K$ and $A_1$. (3) If there are several ways to give up relationships, minimize the sum of the affection levels of the relationships given up. However, the number of students is very large, so it is hard to find a way that satisfies these conditions. When the conditions are satisfied, find the minimum sum of the affection levels of the relationships given up.

The first line contains the number of students $N(3 \leq N \leq 10\ 000)$ and the number of romantic relationships $M(N \leq M \leq 100\ 000)$. The next $M$ lines each contain three integers $a_i$, $b_i$, $c_i$ and a status $d_i$, separated by spaces. $(1 \leq a_i < b_i \leq N; 1 \leq c_i \leq 10\ 000)$ Students $a_i$ and $b_i$ have a relationship with affection level $c_i$. If $d_i$ is 1, the relationship is already established. If $d_i$ is 0, it is not. Any two students are connected by one or more relationships. No pair of students has more than one relationship. No $K$-gon made only of established relationships exists.

Print the minimum sum of the affection levels of the relationships that are given up.