题解中有暴力 + 剪枝建图的方法，貌似是可以卡到 $\mathcal O(n^2)$ 的。

#include <bits/stdc++.h>
using namespace std;
int n=1e5, V=1e9;

int main() {

	printf("%d %d\n", n, V);
	printf("%d %d\n", n, n+1);
	for(int i=1; i<=n; ++i) {
		printf("%d %d %d\n", i, i, n+i);
	}
	return 0;
}

用以上程序造了一组数据，如果数据合法的话，貌似卡掉了一些题解

link1

link2

link3

以及最优解的前几名（