Disrupting the Training Path

Mirko and Slavko are training for the annual two‐person bicycle marathon in Croatia. They choose a cyclic training route that starts and ends at the same city, uses a number of roads without revisiting any city and does not ride on the same road twice. Because they switch seats in every city to share the wind, they want the route to have an even number of roads so that both cyclists ride the same distance.

The country has N cities and M roads. Exactly N−1 of these roads are paved and form a connected tree, while the remaining M−(N−1) roads are unpaved dirt roads. Each city is incident to at most 10 roads. Rival competitors want to block all even‐length cyclic routes that satisfy the above restrictions by placing barriers on some of the dirt roads. For each dirt road, a barrier can be set up at a given positive cost. Barriers cannot be placed on paved roads.

A simple observation shows that any cycle in the complete road network must use at least one unpaved road. In fact, given the tree structure of paved roads, every dirt road e together with the unique paved path between its endpoints forms a cycle. If the endpoints of e lie in different parts of the bipartition (which is unique since the paved roads form a tree), the paved path has odd length and adding e (which connects two different parts) makes the cycle even – such an extra edge is dangerous and must be blocked. Dirt roads that connect vertices in the same part of the bipartition (we call these safe by themselves) form an odd cycle when considered on their own. However, if two or more such dirt roads are left without a barrier, they may interact via the unique paved paths to create an even cycle. (For example, if two dirt roads share a vertex, one can combine parts of their corresponding cycles to obtain an even cycle.)

Thus, to ensure that there is no even cycle (i.e. no valid training route), the competitors must place barriers on all dirt roads that connect cities in different parts, and among the dirt roads connecting cities in the same part they must leave at most one unblocked. Your task is to compute the minimum total cost of placing barriers so that no even cycle exists in the remaining road network.

Input constraints: 1 ≤ N ≤ 10⁵, 1 ≤ M ≤ 10⁵. Each unpaved road (dirt road) has a positive integer cost. Cities are numbered from 1 to N. The input is guaranteed to be such that the paved roads form a tree and each city is incident to at most 10 roads.

inputFormat

The first line contains two integers N and M — the number of cities and the number of roads.

Each of the next M lines describes a road. A road description is given as follows:

• If the road is paved, the line contains three integers: u, v, and 1, indicating that there is a paved road between cities u and v.
• If the road is unpaved (dirt road), the line contains four integers: u, v, 0, and c, where c (a positive integer) is the cost to set up a barrier on that road.

It is guaranteed that exactly N−1 of the roads are paved and they connect all cities (i.e. form a tree), and that each city is incident to at most 10 roads.

outputFormat

Output a single integer — the minimum total cost to set up barriers so that there is no even-length cycle (i.e. no valid training route) in the remaining road network.

sample

3 3
1 2 1
2 3 1
1 3 0 5

0