链接

题意：给定一个无向连通图的点个数n和边条数m。为使最小生成树的大小等于从顶点1到顶点n的最短路长度，输出m条边。

题解：首先要搞懂最小生成树，把边数从小到大排序，每次选最小的边，直到所有顶点都在最小生成树中。所以1-n的边权一定是最小的并且不能相等。多余的边随便添加，前提是不能比前n个添加的小，并且不能有重边。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <math.h>
#include <string>
#define PI 3.14159
using namespace std;

typedef pair<int,int> PII;
typedef long long ll;
const int MAX_INT =  0x3f3f3f3f;
const int N = 1e5+15;
const int mod = 1e9+7;

void solve()
{
    int n,m;
    cin>>n>>m;
    
    int cnt = 0;
    
    for(int i=1;i<n;i++)
    {
        cout<<i<<" "<<i+1<<" "<<++cnt<<endl;
    }

    int bg = 1;
    int dit = 2;
    while(cnt<m)
    {
        if(bg+dit<=n)
        {
            cout<<bg<<" "<<dit+bg<<" "<<++cnt<<endl;
            bg++;
        }
        else
        {
            bg = 1;
            dit++;
        }
        
    }
}

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    
    int T = 1;
    cin>>T;
    while(T--)
    {
        solve();
    }
}