Tyvj Communication Network

Special for beginners, ^_^

Problem Description

Tyvj is already a year old, and the site has grown from a few initial users to tens of thousands. As the Tyvj site gradually grows, the number of administrators keeps increasing. As the liaison of Tyvj's management, you want to find some communication channels so that every pair of administrators can be in touch (directly or indirectly). Tyvj is a non-profit website without much profit, so you must keep the cost as low as possible.

You already know that Tyvj's communication channels fall into two categories: one is mandatory channels, which you must all include regardless of their price; the other is optional channels, from which you may pick some to form the final communication network among administrators. The data guarantees that the given channels can connect all administrators.

Input Format

The first line: $n,m$, meaning Tyvj has $n$ administrators and there are $m$ communication channels.

Lines $2$ through $m+1$: each line has four non-negative integers $p,u,v,w$.

When $p=1$, this channel is a mandatory channel.

When $p=2$, this channel is an optional channel; $u,v,w$ means this entry describes a communication channel between administrators $u$ and $v$: $u$ can receive $v$'s messages and $v$ can also receive $u$'s messages, and $w$ is the cost.

Output Format

The minimum communication cost.

Sample Input 1

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

Sample Output 1

9

Hint

1-2-3-4-1: there are four mandatory channels forming a cycle, so they can reach each other. To connect all administrators you need to connect administrator 2 and administrator 5; choose the channel of cost 5, so the total cost is 9.

There may be multiple communication channels between $u$ and $v$; your program should sum up all mandatory channels between $u$ and $v$.

Constraints

1s, 1024KiB for each test case.

For $30\%$ of the data, $n\le10,\ m\le100$.

For $50\%$ of the data, $n\le200,\ m\le1000$.

For $100\%$ of the data, $n\le2000,\ m\le10000$.