传送门：
本题是一个树上的问题——DFS。
一棵N个结点的树，其结点为1~N。树具有N-1条边，每一条边具有一个权值。
1~N具有N!个不同的排列，第i（1≤i≤N!）个排列记为P[i]，第i个排列中的第j（1≤j≤N）个数记为P[i][j]。
对于第i个排列P[i]，在树上沿最短路依次通过P[i][1]~P[i][N]。记最短路的权值和为S[i]，求解：
$\sum_{i=1}^{N!} S_i \mod M$
考虑1~N间的两个不同的数u、v。在N!个排列中，v恰好为u的后继的排列数为(N-1)!。于是，若记u→v的最短路为D(u,v)，则所求答案为：
$(N-1)!\:*\sum_{u\ne v}D(u,v)\mod M$
现在，考虑式：
$f(T)=\sum_{u<v}D(u,v)\cdots(*)$
接下来，考虑树的结点与边。无向树上的每一个结点都是树的割顶，每一条边都是树的桥。于是，树上的每一条边将树划分为两棵子树。考虑连接结点u、v的边：这条边将树划分为以结点u为根的子树、和以结点v为根的子树。设以结点u为根的子树的结点数为cnt[u]，则以结点v为根的子树的结点数为cnt[v]=N-cnt[u]。
回到式（*）中，则边(u,v)对式子的贡献为$w(u,v)*cnt[u]*cnt[v]$。
考虑通过DFS预处理cnt[]：选取某一个结点作为根结点，通过DFS预处理以结点u为根的子树的结点数cnt[u]。之后，遍历树上的边：连接结点v与其父结点的边，其对式子的贡献为$w(p[v],v)*cnt[v]*(N-cnt[v])$。
考虑到双向，答案为$ans=2(N-1)!\:*f(T)\mod M$。
参考程序如下：
#includeusing namespace std;#define MAX_N 100005const int64_t mod = 1e9 + 7;struct arrow{ int to; int cost; arrow(int to = 0, int cost = 0) : to(to), cost(cost) {}};int64_t fact[MAX_N];void init(void){ fact[0] = 1; for (int i = 1; i < MAX_N; i++) fact[i] = fact[i - 1] * i % mod;}int n;vector adj[MAX_N];int64_t ans;int cnt[MAX_N];void dfs_cnt(int u, int p){ cnt[u] = 1; for (int i = 0; i < adj[u].size(); i++) { int v = adj[u][i].to; if (v == p) continue; dfs_cnt(v, u); cnt[u] += cnt[v]; }}void dfs_calc(int u, int p){ for (int i = 0; i < adj[u].size(); i++) { int v = adj[u][i].to; int w = adj[u][i].cost; if (v == p) continue; int64_t cur = 1ll * cnt[v] * (n - cnt[v]); ans += cur * w % mod; ans %= mod; dfs_calc(v, u); }}int main(void){ ios::sync_with_stdio(false); init(); while (cin >> n) { memset(cnt, 0, sizeof(cnt)); for (int i = 1; i < n; i++) { int u, v, w; cin >> u >> v >> w; adj[u].push_back(arrow(v, w)); adj[v].push_back(arrow(u, w)); } ans = 0; dfs_cnt(1, -1); dfs_calc(1, -1); cout << 2ll * ans % mod * fact[n - 1] % mod << endl; for (int i = 1; i <= n; i++) adj[i].clear(); } return 0;}