You are given a binary weighted graph of n vertices and m edges (n <= 100, m <= n * (n — 1) / 2) . Consider all possible spanning tree, its cost is the xor sum of its edges, ans its cost is added to the final answer.

Input:

n m (n <= 100, m <= n * (n - 1) / 2

u v w (1 <= u < v <= n, w is 0 or 1)

Output:

sum of cost of all spanning tree with mod 1e9 + 7

My current approach stops with using Kirchhoff theorem at some point of the problem but I don't know what be the elements of the Laplacian Matrix.

I hope someone will notice and help me to solve this problem.