给定一个无向简单图(即无重边无自环). 每条边都有一个权值. 这个图的一个鸽, 指的是将它的点集划分为两个不重不漏的集合S和T. 这个鸽的权值, 是所有两个端点分别属于S和T的边的权值的异或和(即, S内部的边和T内部的边都不算). 现在问这个图的鸽的所有可能权值的和是多少. 由于这个数很大, 只需要输出前9位, 不足9位则全部输出.
输入描述:
第一行两个数n和m表示图的点数和边数(0<n<100001,0<m<200001).
之后m行每行3个数表示一条边的两个端点和这条边的权值. 点的编号从1到n,权值为0到10^9之间的整数.
输出描述:
输出答案
示例1
说明
所有的鸽中,只有把1和2分开的鸽才有非0的权值, 这个权值只能是1. 所以所有可能的权值的和是0+1=1.