Prim算法：

#include <bits/stdc++.h>
using namespace std;
struct node{int u,v,w;};
// Prim：适合稠密图，这里用邻接矩阵实现，方便 n<=100
int n,m;
vector<vector<int>> g;
//dis:表示从当前已加入生成树的点，到点 i 的最小连接边的权值
vector<int> vis,dis,pre;
const int INF=1e9;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    g.assign(n+1,vector<int>(n+1,INF));
    for(int i=1;i<=n;i++) g[i][i]=0;
    for(int i=0;i<m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        if(u>v) swap(u,v);
        // 可能有重边，保留最小造价
        if(w<g[u][v]){
            g[u][v]=g[v][u]=w;
        }
    }
    vis.assign(n+1,0);
    dis.assign(n+1,INF);
    pre.assign(n+1,0);
    int st=1; // 从 1 号点开始扩展
    dis[st]=0;
    pre[st]=0;
    for(int it=1;it<=n;it++){
        int x=0,best=INF;
        // 选一个未加入生成树且 dis 最小的点 x
        for(int i=1;i<=n;i++){
            if(!vis[i] && dis[i]<best){
                best=dis[i];
                x=i;
            }
        }
        if(x==0) break; // 理论上不会发生（题目保证连通）
        vis[x]=1; // 把 x 加入生成树集合
        // 用 x 去更新其它点到生成树的最小连接边
        for(int y=1;y<=n;y++){
            if(!vis[y] && g[x][y]<dis[y]){
                dis[y]=g[x][y];
                pre[y]=x; // 记录 y 的前驱（即 MST 中连接 y 的那条边来自 x）
            }
        }
    }
    // 收集 MST 的 n-1 条边：每个点(除起点)都会有一个 pre
    vector<node> ans;
    ans.reserve(n-1);
    for(int v=1;v<=n;v++){
        if(v==st) continue;
        int u=pre[v];
        int a=u,b=v;
        if(a>b) swap(a,b);
        ans.push_back({a,b,0});
    }
    // 按(u,v)排序输出，匹配题目常见格式
    sort(ans.begin(),ans.end(),[](const node& x,const node& y){
        if(x.u==y.u) return x.v<y.v;
        return x.u<y.u;
    });
    for(auto &e:ans) cout<<e.u<<" "<<e.v<<"\n";
    return 0;
}

Kruskal

#include <bits/stdc++.h>
using namespace std;
struct node{int u,v,w;};
int n,m,cnt=0;
vector<node> b,a;
vector<int> pa,sz;
// 初始化并查集：每个点自成一个集合
void init(int n){
    pa.resize(n+1);
    sz.assign(n+1,1);
    for(int i=1;i<=n;i++) pa[i]=i;
}
// 查找根节点（带路径压缩）
int findr(int x){
    if(pa[x]!=x) pa[x]=findr(pa[x]);
    return pa[x];
}
// 合并两个集合（按大小合并）
void join(int x,int y){
    int rx=findr(x),ry=findr(y);
    if(rx==ry) return;
    if(sz[rx]<sz[ry]) swap(rx,ry);
    pa[ry]=rx;
    sz[rx]+=sz[ry];
}
// Kruskal：按边权从小到大选边，避免成环
void kruskal(){
    a.clear();
    a.reserve(n-1);
    cnt=0;
    for(int i=0;i<m;i++){
        int u=b[i].u,v=b[i].v;
        if(findr(u)!=findr(v)){
            join(u,v);
            a.push_back({u,v,b[i].w}); // 记录选中的边
            cnt++;
            if(cnt==n-1) break; // 生成树边数够了就结束
        }
    }
}
bool cmpw(const node& x,const node& y){return x.w<y.w;}
bool cmpuv(const node& x,const node& y){
    if(x.u==y.u) return x.v<y.v;
    return x.u<y.u;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    b.resize(m);
    for(int i=0;i<m;i++){
        cin>>b[i].u>>b[i].v>>b[i].w;
        if(b[i].u>b[i].v) swap(b[i].u,b[i].v); // 统一保证 u<=v，便于最终排序输出
    }
    init(n);
    sort(b.begin(),b.end(),cmpw); // 按权值排序
    kruskal(); // 跑 Kruskal 得到 MST
    sort(a.begin(),a.end(),cmpuv); // 按(u,v)排序，匹配题目输出习惯
    for(auto &e:a) cout<<e.u<<" "<<e.v<<"\n";
    return 0;
}