作为当代大学生，不仅要学好专业知识，还要有强健的体魄来支撑每天高强度的学习与工作（只是不知道能不能防脱发啊QAQ）。而跑步可能是大多数人的选择，它有……（此处省略）等好处。
zzz也喜欢利用每天的空闲时间跑个步（说的我差点信了QAQ），但这一次，zzz因为准备这一次程序设计竞赛废寝忘食，等他回过神来，发现离比赛开始只剩下了1分钟，哪怕他以最快速度飞奔去机房也来不及，不过幸运的是，他召唤出了Enal大魔法师。
Enal大魔法师在学校随机生成n个传送点，同时也构建了m道单向超光速通道（允许两个传送点之间存在多条通道，但反向通道不通）用以连接两个固定的传送点，而通道中也因为强大的魔法而散落有能量点。如果两个传送点之间存在通道，则zzz可以在这条通道的起点毫不费时也毫不费力地传送到这条通道的终点。
Enal大魔法师承诺可以让zzz按时参加比赛，但作为释放“传送”技能的补偿，zzz需要在至少一个传送点搜集足够多的能量值（使之能够满足Enal的最低要求能量值t），否则，Enal也无能为力，而一个传送点的能量在离开了这个传送点之后便会消散，所以不能叠加，zzz本就焦头烂额，所以只好向你求救！
一个传送点可能的能量值为：从与该点直接相连且能过通过的所有通道的散落能量点值中任意挑选两个值进行异或运算后的结果（如果非要自己异或自己也是可以的哈）。（特别的，若该点没有通道，则该点能量值为0）
（此处为对于题中异或运算的简单解释：将两个数均写成二进制形式，可适当补前导零，对于同一位上的二进制，如果两数不同，则最后结果中这一位上为1，否则为0；再简单点说，就是二进制下的不进位加法！）

第一行输入n, m, t。  1 ≤ n ≤ 105   0 ≤ m ≤ 2 × n   0 ≤ t ＜ 231 （题目保证不存在自己到自己的通道）
接下来m行，每行一个整数u, v, w，表示从u号传送点到v号传送点有一条通道，通道中散落的能量点值为w。
1 ≤ u, v ≤ n 且 u != v    0 ≤ w ＜ 231

如果zzz能够按时参加比赛，则输出他在传送点可能搜集到的能量值的最大值，否则输出“QAQ”（输出不含有引号)

3 2 1
1 2 3
1 3 1

2

逆乾 WIT第二届程序设计竞赛(现场赛)