略微变一下Prim算法即可

#include <bits/stdc++.h>
using namespace std;
const int N = 305,INF = 0x3f3f3f3f;

int g[N][N],n,m;
int dist[N];
bool st[N];

int prim()
{
    memset(dist,INF,sizeof(dist));
    int res = 0;
    for(int i=0;i<n;i++)
    {
        int t = -1;
        for(int j=1;j<=n;j++)
            if(!st[j] && (t == -1 || dist[j]<dist[t]))
                t = j;
        if(i && dist[t] == INF) return INF;
        if(i) res = max(res,dist[t]);
        for(int j=1;j<=n;j++) dist[j] = min(dist[j],g[j][t]);
        st[t] = true;
    }
    return res;
}

int main()
{
	memset(g,0x3f,sizeof(g));
	cin >> n >> m;
	int w = 0;
	while(m--)
	{
		int u,v,c;
		cin >> u >> v >> c;
		g[u][v] = g[v][u] = min(g[u][v],c);
		w+=c;
	}
	int t = prim();
	cout << n-1 << " " << t;
	return 0;
}