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。