{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"During the Three-Kingdom period, there was a general named Xun Lu who belonged to Kingdom Wu. Once his troop were chasing Bei Liu, he was stuck in the Ba Gua Zhen from Liang Zhuge.\nThe puzzle could be considered as an undirected graph with $N$ vertexes and $M$ edges. Each edge in the puzzle connected two vertexes which were $u_i$ and $v_i$ with a length of $w_i$.\nLiang Zhuge had great interests in the beauty of his puzzle, so there were no self-loops and between each pair of vertexes, there would be at most one edge in the puzzle.\nAnd it was also guaranteed that there was at least one path to go between each pair of vertexes.\n\nFortunately, there was an old man named Chengyan Huang who was willing to help Xun Lu to hack the puzzle. Chengyan told Xun Lu that he had to choose a vertex as the start point,\nthen walk through some of the edges and return to the start point at last. During his walk, he could go through some edges any times. Since Liang Zhuge had some mysterious magic,\nXun Lu could hack the puzzle if and only if he could find such a path with the maximum `XOR` sum of all the edges length he has passed. If the he passed some edge multiple times,\nthe length would also be calculated by multiple times. Now, could you tell Xun Lu which is the maximum `XOR` circuit path in this puzzle to help him hack the puzzle?"}},{"title":"Input","value":{"format":"MD","content":"The first line of the input gives the number of test cases, $T$($1\\leq T\\leq 30$). $T$ test cases follow.\n\nEach test case begins with two integers $N$($2\\leq N\\leq 5\\times 10^4$) and $M$($1\\leq M\\leq 10^5$) in one line. Then $M$ lines follow. Each line contains three integers\n$u_i$, $v_i$ and $w_i$($1\\leq u_i, v_i\\leq N$, $0\\leq w_i\\leq 2^{60}-1$) to describe all the edges in the puzzle."}},{"title":"Output","value":{"format":"MD","content":"For each test case, output one line containing `Case #x: y`, where $x$ is the test case number (starting from $1$) and $y$ is the maximum `XOR` sum of one circuit\npath in the puzzle."}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n3 3\n1 2 1\n1 3 2\n2 3 0\n6 7\n1 2 1\n1 3 1\n2 3 1\n3 4 4\n4 5 2\n4 6 2\n5 6 2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 3\nCase #2: 3\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"MD","content":"A `XOR` takes two bit patterns of equal length and performs the logical exclusive `OR` operation on each pair of corresponding bits. The result in each position is $1$\nif only the first bit is $1$ or only the second bit is $1$, but will be $0$ if both are $0$ or both are $1$. In this we perform the comparison of two bits, being $1$ if the\ntwo bits are different, and $0$ if they are the same."}}]}