题号：NC17667
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
Niuniu is (p)reviewing NOIP 2017 problems.
Maybe you have heard NOIP 2017 Day 2 Problem 2 Treasure.
You can find the problem at https://www.nowcoder.com/acm/contest/154/1002. He found that the official data is very weak. Many contestants accepted this problem with search solutions or wrong solutions.
We want to find the sum of weight of all rooted spanning tree.
The weight of a rooted spanning tree is defined as follows.
Enumerate all edges in the tree.
The contribution of an edge is its weight times its depth in the rooted tree.
The depth of a vertex is the number of edges from the root to the vertex.
As the answer might be very large, you only need to output the answer mod 1000000007.
输入描述:
The first line contains two integers n, m, which are the number of vertices and the number of edges.
In the following m lines, each line contains three integers x, y, z, which means there is an edge between x and y, whose weight is z.
1 <= n <= 12
1 <= m <= 1000
1 <= x <= n
1 <= y <= n
1 <= z <= 5000
输出描述:
You should ouput one line, which contains the answer.
备注:
There might be multiple edges between two vertices.