#LQ1591. 最优路径

最优路径

问题描述

给出一个具有 NN 个点、MM 条边的无向图(可能存在重边和自环)。其中每条边都有一个 ww 属性表示无向边的权重。

你可以从这个图中任意选两个不同的点 startend,并以 start 作为起点, end 作为终点找出一条从 startend 的路径(这条路径可以多次经过同一个点,也可以多次经过同一条边),将这条路径上经过的所有边的权重求一个异或和便得到了这条路径的风险值。

小蓝想要找到一条风险值最小的路径,请问最小的风险值是多少?

输入格式

第一行输入两个整数 NNMM。 接下来输入 MM 行,每行三个整数 uuvvww,表示一条无向边连接 uuvv 两个点,权重为 ww

输出格式

输出一个整数表示最小的风险值。如果不存在任何一条满足题意的路径,输出 -1

3 4
1 1 9
2 3 3
2 3 8
3 3 1
2

样例说明

先走第二条边,再走第四条边,风险值 31=23⊕1=2

评测用例规模与约定

对于 60%60\% 的评测用例:1N501≤N≤501M1031≤M≤10^3

对于 100%100\% 的评测用例:1N5001≤N≤5001M1041≤M≤10^41u,vN1≤u,v≤N1w1031≤w≤10^3