题目描述

给你一个 $N$ 个点 $M$ 条边的有向图，第 $i$ 条边从结点 $A_i$ 连向结点 $B_i$，权值为 $W_i$。

求所有从 $1$ 到 $N$ 的路径中，可以重复经过同一个点和同一条边，路径上所有边权值的异或和的最小值。

输入格式

第一行两个整数 $N,M(2\le N\le 1000,0\le M\le 1000)$。
接下来 $M$ 行，每行三个整数 $A_i,B_i,W_i(0\le W_i<2^{10})$。

输出格式

如果不存在 $1$ 到 $N$ 的路径，输出一行一个整数 $-1$。

否则，输出一行一个整数表示答案。

输入输出样例 #1

输入 #1

3 3
1 2 4
2 3 5
1 3 2

输出 #1

1

输入输出样例 #2

输入 #2

4 4
1 4 7
4 2 2
2 3 4
3 4 1

输出 #2

0

输入输出样例 #3

输入 #3

999 4
1 2 9
2 1 8
1 2 7
1 1 6

输出 #3

-1

说明/提示

样例 1 解释

路径(边 $1$，边 $2$) 的边权异或和为 $1$。

样例 2 解释

路径(边 $1$，边 $2$，边 $3$，边 $4$) 的边权异或和为 $0$。

注意 $N$ 可能出现在路径的中间。

样例 3 解释

如果不存在 $1$ 到 $N$ 的路径，输出 $-1$。