RT

本题唯一篇题解复杂度有误，可能是数据水放过去了。只要一个菊花图即可将其卡成 $n^2\log n$。

hack样例:

#include <bits/stdc++.h>
using namespace std;
signed main() {
	freopen("1.in","w",stdout);
	srand(114514);
	int n = 100000, k = 810;
	cout<<n<<' '<<k<<"\n";
	for (int i = 2; i <= n; ++i) cout<<1<<" "<<i<<" "<<rand()%n+1<<"\n";
	return 0;
}

所以请求通过我的题解。复杂度是严格 $n\log^2 n$ 的。