Cut
题号:NC14251
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 32 M,其他语言64 M
64bit IO Format: %lld

题目描述

给定一个无向简单图(即无重边无自环). 每条边都有一个权值. 这个图的一个鸽, 指的是将它的点集划分为两个不重不漏的集合S和T. 这个鸽的权值, 是所有两个端点分别属于S和T的边的权值的异或和(即, S内部的边和T内部的边都不算). 现在问这个图的鸽的所有可能权值的和是多少. 由于这个数很大, 只需要输出前9位, 不足9位则全部输出.

输入描述:

第一行两个数n和m表示图的点数和边数(0<n<100001,0<m<200001).
之后m行每行3个数表示一条边的两个端点和这条边的权值. 点的编号从1到n,权值为0到10^9之间的整数.

输出描述:

输出答案
示例1

输入

复制
2 1
1 2 1

输出

复制
1

说明

所有的鸽中,只有把1和2分开的鸽才有非0的权值, 这个权值只能是1. 所以所有可能的权值的和是0+1=1.