#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 10005
#define INF 0x3f3f3f3f
using namespace std;
struct node
{
int id,num;
}maps[N][N];
int w[N],dis[N];
bool visit[N];
int n,m;
int prime(int flagg)
{
int a=0;
if(flagg==1)
a=1;
memset(visit,false,sizeof(visit));
memset(dis,INF,sizeof(dis));
dis[1]=0;
visit[1]=true;
for(int i=a; i<=n; i++)
{
if(i==1||maps[1][i].id!=1)
continue;
dis[i]=maps[1][i].num;
}
int minn,pos,j,answer=0;
for(j=a; j<n; j++)
{
minn=INF;
for(int i=a; i<=n; i++)
{
if(!visit[i]&&(dis[i]<minn))
{
minn=dis[i];
pos=i;
}
}
if(minn==INF)
break;
visit[pos]=true;
answer+=minn;
for(int i=a; i<=n; i++)
{
if(!visit[i]&&(maps[pos][i].num<dis[i])&&maps[pos][i].id==1)
{
dis[i]=maps[pos][i].num;
}
}
}
if(j==n)
return answer;
else
return INF;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1; i<=m; i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
maps[a][b].num=maps[b][a].num=c;
maps[a][b].id=maps[b][a].id=1;
}
for(int i=1; i<=n; i++)
{
scanf("%d",&w[i]);
}
for(int i=1; i<=n; i++)
{
if(w[i]!=-1)
{
maps[0][i].id=maps[i][0].id=1;
maps[0][i].num=maps[i][0].num=w[i];
}
}
int answer1=prime(1);
int answer2=prime(2);
int minn=min(answer1,answer2);
printf("%d\n",minn);
return 0;
}
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 10005
#define INF 0x3f3f3f3f
using namespace std;
struct node
{
int id,num;
}maps[N][N];
int w[N],dis[N];
bool visit[N];
int n,m;
int prime(int flagg)
{
int a=0;
if(flagg==1)
a=1;
memset(visit,false,sizeof(visit));
memset(dis,INF,sizeof(dis));
dis[1]=0;
visit[1]=true;
for(int i=a; i<=n; i++)
{
if(i==1||maps[1][i].id!=1)
continue;
dis[i]=maps[1][i].num;
}
int minn,pos,j,answer=0;
for(j=a; j<n; j++)
{
minn=INF;
for(int i=a; i<=n; i++)
{
if(!visit[i]&&(dis[i]<minn))
{
minn=dis[i];
pos=i;
}
}
if(minn==INF)
break;
visit[pos]=true;
answer+=minn;
for(int i=a; i<=n; i++)
{
if(!visit[i]&&(maps[pos][i].num<dis[i])&&maps[pos][i].id==1)
{
dis[i]=maps[pos][i].num;
}
}
}
if(j==n)
return answer;
else
return INF;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1; i<=m; i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
maps[a][b].num=maps[b][a].num=c;
maps[a][b].id=maps[b][a].id=1;
}
for(int i=1; i<=n; i++)
{
scanf("%d",&w[i]);
}
for(int i=1; i<=n; i++)
{
if(w[i]!=-1)
{
maps[0][i].id=maps[i][0].id=1;
maps[0][i].num=maps[i][0].num=w[i];
}
}
int answer1=prime(1);
int answer2=prime(2);
int minn=min(answer1,answer2);
printf("%d\n",minn);
return 0;
}