C. Complete the MST
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

As a teacher, Riko Hakozaki often needs to help her students with problems from various subjects. Today, she is asked a programming task which goes as follows.

You are given an undirected complete graph with $n$ nodes, where some edges are pre-assigned with a positive weight while the rest aren't. You need to assign all unassigned edges with non-negative weights so that in the resulting fully-assigned complete graph the XOR sum of all weights would be equal to $0$.

Define the ugliness of a fully-assigned complete graph the weight of its minimum spanning tree, where the weight of a spanning tree equals the sum of weights of its edges. You need to assign the weights so that the ugliness of the resulting graph is as small as possible.

As a reminder, an undirected complete graph with $n$ nodes contains all edges $(u, v)$ with $1 \le u < v \le n$; such a graph has $\frac{n(n-1)}{2}$ edges.

She is not sure how to solve this problem, so she asks you to solve it for her.

Input

The first line contains two integers $n$ and $m$ ($2 \le n \le 2 \cdot 10^5$, $0 \le m \le \min(2 \cdot 10^5, \frac{n(n-1)}{2} - 1)$)  — the number of nodes and the number of pre-assigned edges. The inputs are given so that there is at least one unassigned edge.

The $i$-th of the following $m$ lines contains three integers $u_i$, $v_i$, and $w_i$ ($1 \le u_i, v_i \le n$, $u \ne v$, $1 \le w_i < 2^{30}$), representing the edge from $u_i$ to $v_i$ has been pre-assigned with the weight $w_i$. No edge appears in the input more than once.

Output

Print on one line one integer  — the minimum ugliness among all weight assignments with XOR sum equal to $0$.

Examples
Input
4 4
2 1 14
1 4 14
3 2 15
4 3 8

Output
15

Input
6 6
3 6 4
2 4 1
4 5 7
3 4 10
3 5 1
5 2 15

Output
0

Input
5 6
2 3 11
5 3 7
1 4 10
2 4 14
4 3 8
2 5 6

Output
6

Note

The following image showcases the first test case. The black weights are pre-assigned from the statement, the red weights are assigned by us, and the minimum spanning tree is denoted by the blue edges.
{"ft_lang_label":"__label__en","ft_lang_prob":0.9165735,"math_prob":0.9988593,"size":2086,"snap":"2021-31-2021-39","text_gpt3_token_len":624,"char_repetition_ratio":0.12487993,"word_repetition_ratio":0.010256411,"special_character_ratio":0.34659636,"punctuation_ratio":0.07674944,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9983657,"pos_list":[0,1,2],"im_url_duplicate_count":[null,1,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-07-28T10:01:40Z\",\"WARC-Record-ID\":\"<urn:uuid:39fcd0a3-ce69-4f56-a738-f7435130f98b>\",\"Content-Length\":\"58473\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:25795d20-50cd-4d37-bece-9ae886683431>\",\"WARC-Concurrent-To\":\"<urn:uuid:21928266-fd2b-40d3-8ef3-ec882ad8582a>\",\"WARC-IP-Address\":\"213.248.110.126\",\"WARC-Target-URI\":\"https://codeforces.com/problemset/problem/1508/C\",\"WARC-Payload-Digest\":\"sha1:UTQQH33VGNQPSAUUFCNXV6TINUU72ZQX\",\"WARC-Block-Digest\":\"sha1:RVRITR2HDRZCDXFNKTQZSQQKF5V46JUU\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-31/CC-MAIN-2021-31_segments_1627046153709.26_warc_CC-MAIN-20210728092200-20210728122200-00341.warc.gz\"}"}