Floyd

有n个顶点和m条有向边，边权可为负，保证全图没有负权环。允许重边和自环。令D(i,j)为i到j的最短距离，不可达时定义为10000000000000000；D(i,i)=0。

令F=10000000000000000，整数S初值为0。对所有有序点对(i,j)，包括i=j，执行S=S XOR (D(i,j)+F)，输出最终S。XOR表示整数按位异或，不是求和。

输入格式

第一行n m；随后m行u v w表示u到v的有向边。1<=n<=500，0<=m<=250000，1<=u,v<=n，-1000000000<=w<=1000000000。保证无负环。

输出格式

输出S，一个非负整数。

输入样例

2 3
1 2 1
1 2 3
2 2 0

输出样例

28300427233787905

样例说明

四个D值为0、1、F、0，因此应异或F、F+1、2F、F。采用64位整数，S必须初始化为0。

补全版本与公开来源

原站当前仅返回建设中或教师团队资格提示，未取得其完整原文。本题依据公开资料整理并按授权补全，具体约定：按公开全文补原站受限题面；明确S初始0，保持无负环、D(i,i)=0、不可达F及所有有序对(D+F)异或；原样例独立Bellman-Ford核算一致。。本版本不冒称官方完整原文或原始评测数据。原站链接：https://ybt.ssoier.cn/problem_show.php?pid=1421。公开资料：https://developer.aliyun.com/article/1285791。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共6个测试点，非原站或官方原始数据。总分100分。