prim求最短路（稀疏）

//prim求最短路（神似dijkstra） 
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
const int N=1e3+10;

int dis[N],g[N][N];
bool st[N];
int n,m,res;

int prim()
{
	memset(dis,0x3f,sizeof dis);
	
	for(int i=0;i<n;i++)
	{
		int t=-1;
		for(int j=1;j<=n;j++)
		if(!st[j]&&(t==-1||dis[j]<dis[t]))
		t=j;
		
		st[t]=true;
		if(i&&dis[t]==0x3f)return 0x3f;      //如果i不为1(不是第一个点，第一个点的dis为无穷大） ，并且距离无穷 ，则无法构成最短路 
		if(i)res+=dis[t];    //如果不是第一个点 就将最短路径更新 
		for(int j=1;j<=n;j++)
		dis[j]=min(dis[j],g[t][j]);        //dis存该点到已知点集合的距离，也是唯一与dijkstra不同(dis[j]=dis[t]+g[t][j])
	
	}	return res;
}



int main(void)
{
	memset(g,0x3f,sizeof g);
	cin>>n>>m;
	while(m--)
	{
		int a,b,x;
		cin>>a>>b>>x;
		g[a][b]=g[b][a]=min(g[a][b],x);
	}
	//cout<<res<<endl;
	if(prim())
	cout<<res<<endl;
	else
	puts("impossible");
	return 0;
}