解题思路
给定一条从 1 到 u 的简单路径，允许至多一次选择一个连续边段 [l,r] 把该段内每条边权 w 改为 w⊕x 后再求路径边权和的最小值。等价地看：沿着路径行进时，我们会有三种“状态”：
- 状态 0：尚未开始异或段（之后的某一段可开始，也可以永不开始）；
- 状态 1：正处于异或段中（本段内边权以 w⊕x 计）；
- 状态 2：已结束异或段（之后再以原权 w 行走，不可再开启）。
把“路径上一段用 w⊕x”的限制，转化为分层图最短路（Dijkstra）：
P3757.第3题-米小游的异或最短路
题目内容
给定一个有 n 个结点以及 m 条的带权有向图 G ，以及一个整数 x 。G 中保证没有自环。
米小游初始在结点 1。对于一条从 1 到 u 的长度k 为的 简单路径，设其经过的 点 为p1,p2,...,pk+1，其中 p1=1,pk+1=u ，且对于所有 1≤i≤k，G 中都存在一条 pi 从到 pi+1 的有向边。这条路径的代价计算方式如下：
- 米小游可以选择两个整数 l,r ，满足 1≤l≤r≤k 。接下来，对于所有的 l≤i≤r，米小游将到这条有向边的边权异或上 x 。也就是说，如果原本这条边的边权为 w ，米小游会将其修改为 w⊕x ，其中 ⊕ 代表按位异或。本操作最多执行一次。
- 路径的代价即为修改之后，所有其经过的边的边权和。
- 从结点 1 到 i 的最小代价即为所有可能的从结点 1 到 i 的路径中的最小代价。
米小游想知道，在这样的代价计算方式下，他到过每个结点的最小代价分别是多少。
注意：为某条路径选定并执行异或操作后，仅用于计算该路径的代价；图本身不会被真正修改，评估其他路径时可重新自由选择 l,r ，或不执行此操作。
【名词解释】
简单路径：不经过重复点和重复边的路径。
输入描述
第一行输入三个整数 n,m,x(2≤n≤105,1≤m≤2⋅105,0≤x≤109) ，分别表示 G 中的结点数量、边数，以及异或时常数。 接下来 m 行，每行输入三个整数 ui,vi,wi(1≤ui,vi≤n,0≤wi≤109) ，代表一条从结点 ui 到 vi，边权为 wi 的有向边。输入保证 G 中不存在自环。
输出描述
输出一行 n 个整数，其中第 i 个整数代表从结点 1 到 i 的路径的最小代价，无法到达则第 i 个整数为 −1 。
样例1
输入
5 5 2
1 2 2
1 5 3
5 3 4
2 4 10
1 4 9
输出
0 0 5 8 1
说明
对于结点 4 ，米小游可以选择路径 1→2→4 ，并将 1→2 和 2→4 两条有向边的边权异或上，代价为 (2⊕2)+(10⊕2)=0+8=8 。可以证明不存在代价小于 8 的路径。 对于结点 3，米小游可以选择路径 1→5→3，并将 1→5 这条有向边的边权异或上 x ，代价为 (3⊕2)+4=1+4=5。可以证明不存在代价小于 5 的路径。
