题目描述

到达月球后，蕾米莉亚一行人要前往月之都，月球是一张有 \(n\) 个点的完全无向图，点的标号是 \(1, \dots, n\)。图中任意两点 \(i\) 和 \(j\) 之间存在一条边，该边的权重为整数 \(i\) 与 \(j\) 的按位异或结果（记作 \(x \oplus \ y\)，例如 \(5 \ \oplus \ 6 = 3\)）。此外，图中还有 \(m\) 条无向边，第 \(k\) 条边连接 \(x_i\) 和 \(y_i\)，权值为 \(w_i\)。

路径长度的定义：从节点 \(x\) 到节点 \(y\) 的路径长度，是该路径上所有边的权值依次按位异或的结果（而非求和）。

蕾米莉亚一行人位于 \(1\) 号点，而月之都位于 \(n\) 号点，蕾米莉亚想要尽快到达月之都，于是拜托你求出从点 \(1\) 到点 \(n\) 的最短路径长度。

输入格式

第一行一个正整数 \(T\) 表示数据组数。

对于每组数据：第一行两个正整数 \(n, m\)，分别表示点数和边数。

接下来 \(m\) 行，每行输入三个整数 \(x_k, y_k, w_k\)，表示一条额外边的两个端点和权值。

\(1 \le T \le 10\)

对于每组测试数据： \(2 \le n \le 10^5, 1 \le m \le 10^5, 1 \le x_k, y_k \le n, 0 \le w_k \le 10^9\)

输出格式

输出 \(T\) 行，每行一个整数表示点 \(1\) 到点 \(n\) 的最短路径长度。

样例输入

1
3 1
2 3 2

样例输出

1

提示

我们可以先走图上的原始边 \(\left(1, 2\right)\)，权值是 \(1\oplus 2 = 3\)，再走额外边 \(\left(2, 3\right)\)，权值是 \(2\)，这样路径长度是 \(2 \oplus 3 = 1\)，可以证明这是在所有路径中路径长度最短的一条。