解题思路

给定一条从 1 到 $u$ 的简单路径，允许至多一次选择一个连续边段 $[l,r]$ 把该段内每条边权 $w$ 改为 $w\oplus x$ 后再求路径边权和的最小值。等价地看：沿着路径行进时，我们会有三种“状态”：

• 状态 0：尚未开始异或段（之后的某一段可开始，也可以永不开始）；
• 状态 1：正处于异或段中（本段内边权以 $w\oplus x$ 计）；
• 状态 2：已结束异或段（之后再以原权 $w$ 行走，不可再开启）。

把“路径上一段用 $w\oplus x$”的限制，转化为分层图最短路（Dijkstra）：

题目内容

给定一个有 $n$ 个结点以及 $m$ 条的带权有向图 $G$ ，以及一个整数 $x$ 。$G$ 中保证没有自环。

米小游初始在结点 $1$。对于一条从 $1$ 到 $u$ 的长度$k$ 为的 简单路径，设其经过的 点 为$p_1,p_2,...,p_{k+1}$，其中 $p_1=1,p_{k+1}=u$ ，且对于所有 $1≤i≤k$，$G$ 中都存在一条 $p_i$ 从到 $p_{i+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≤10^5,1≤m≤2·10^5,0≤x≤10^9)$ ，分别表示 $G$ 中的结点数量、边数，以及异或时常数。 接下来 $m$ 行，每行输入三个整数 $u_i,v_i,w_i(1≤u_i,v_i≤n,0≤w_i≤10^9)$ ，代表一条从结点 $u_i$ 到 $v_i$，边权为 $w_i$ 的有向边。输入保证 $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$ 的路径。