rt，本题爆搜 $\Theta(n2^m)$ 可以使用一个边权全部相同的连通图卡调，数据生成器如下：

#include<bits/stdc++.h>
#define P pair<int,int>
#define fi first
#define se second
#define LL long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=1e5+5;
int tot;P a[N];
int main()
{
    freopen("1.in","w",stdout);
    srand(time(NULL));
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cout<<"100 1000\n";
    for(int i=1;i<100;i++) cout<<i<<" "<<i+1<<" 1\n";
    for(int i=1;i<=100;i++) for(int j=i+2;j<=100;j++) a[++tot]={i,j};
    random_shuffle(a+1,a+1+tot);
    for(int i=1;i<=1000-99;i++) cout<<a[i].fi<<" "<<a[i].se<<" 1\n";
    return 0;
}

（从link蒯的）

经检验，该题解过不了这组数据。