Description

Tyvj has turned one year old, and the website has grown from a few initial users to tens of thousands of users. As Tyvj expands, the number of administrators has also increased. Now, as a liaison officer in Tyvj's management, your task is to identify communication channels so that every pair of administrators can connect (either directly or indirectly). Tyvj is a non-profit website with limited revenue, so you must minimize costs as much as possible.

Currently, you know that Tyvj's communication channels are divided into two categories:

1. Mandatory communication channels: Regardless of cost, you must include all of these.
2. Optional communication channels: You may select some of these as part of the final communication network for administrators.

The given data ensures that the provided channels can connect all administrators.

Input Format

• The first line contains two integers, n and m, representing the number of administrators (n) and the number of communication channels (m).
• The next m lines each contain four non-negative integers: p, u, v, w.
  • If p = 1, the channel is mandatory.
  • If p = 2, the channel is optional.
  • u and v indicate the administrators connected by this channel (bidirectional).
  • w represents the cost of this channel.

Output Format

The minimum total communication cost.

5 6
1 1 2 1
1 2 3 1
1 3 4 1
1 4 1 1
2 2 5 10
2 2 5 5

9

Hint

【Sample Explanation】
The path 1-2-3-4-1 forms a cycle with four mandatory channels, allowing mutual reachability. To ensure all administrators are connected, administrators 2 and 5 must be linked by selecting the channel with a cost of 5, resulting in a total cost of 9.

【Note】
There may be multiple communication channels between nodes u and v. Your program should accumulate all mandatory channels between u and v.

【Data Range】

• For 30% of the data, n ≤ 10, m ≤ 100;
• For 50% of the data, n ≤ 200, m ≤ 1000;
• For 100% of the data, n ≤ 2000, m ≤ 10000.