不晓得啊，我的也是kruskal，只用了47ms
#include<iostream>
#include<cstdlib>
using namespace std;
#define N 1001
#define M 15001
struct NODE
{
	int value;
	int x,y;
	bool flag;
};
 
NODE s[M];
int father[N], rank[N];
bool visit[N];
 
int compare( const void *a, const void *b )
{
	NODE *p=(NODE*)a,*q=(NODE*)b;
	return p->value-q->value;
}
 
void init_set( int n )
{
	int i=0;
	for( i=0; i<n; i++ )
	{
		father[i]=i;
		rank[i]=1;
		visit[i]=false;
	}
}
 
int find_root( int p )
{
	if( father[p] != p ) 
		father[p] = find_root(father[p]);
	return father[p];
}
 
void union_set( int p, int q )
{
	int a, b;
	a = find_root(p);
	b = find_root(q);
	if( rank[a] > rank[b] )
		father[b] = a;
	else if( rank[a] < rank[b] ) 
		father[a] = b;
	else
		father[b] = a, rank[a]++;
}
 
int main( )
{
	int n,m,p,q,i,count,max;
	scanf("%d%d",&n,&m);
	for( i=0; i<m; i++ )
	{
		scanf("%d%d%d",&s[i].x , &s[i].y , &s[i].value);
		s[i].flag=false;
	}
	qsort( s, m, sizeof(NODE), compare );
	init_set( n );
	count=0;max=0;
	for( i=0; i<m && count<n-1; i++ )
	{
		p=s[i].x;q=s[i].y;
		if( !visit[p] || !visit[q] )
		{
			union_set( p, q );
			visit[p]=visit[q]=true;
			count++;
			s[i].flag=true;
			if( s[i].value>max )max=s[i].value;
		}
		else if ( find_root(p) != find_root(q) )
		{
			union_set( p, q );
			visit[p]=visit[q]=true;
			count++;
			s[i].flag=true;
			if( s[i].value>max )max=s[i].value;
		}
	}
	printf("%d\n%d\n",max,count);
	count=0;
	for( i=0; i<m && count<n-1; i++ )
		if( s[i].flag )
		{
			printf("%d %d\n",s[i].x,s[i].y);
			count++;
		}
	return 0;
}