这道题用最小生成树来完成，我选用的是kruskal（克鲁斯卡尔）来完成。

这道题目在克鲁斯卡尔模板的基础上，有变动的地方只有2处：

1.因为必须从一个点出发，而最小生成树最后会让所有点都连通，所以最优的是从c[i]值最低的点出发，所以最后的total要加上最小的c[i]值。

2.因为这道题目的权值很特殊，它包含了2*路的长度（来回走两次）+起点的c[i]+终点的c[i]（这个也要花费时间），在读入的时候直接处理就可以了。

代码就贴在这，因为考虑可能有些题目会卡输入，用了快读，介意的自己改一下就行了（滑稽）

1 #include
     
       2 using namespace std; 3 int n,p,c[100010],fa[100010]; 4 int read() 5 { 6    int x=0,f=1; 7    char ch=getchar(); 8    while(ch<'0'||ch>'9'){ 9        if(ch=='-')10            f=-1;11        ch=getchar();12    }13    while(ch>='0'&&ch<='9'){14        x=(x<<1)+(x<<3)+(ch^48);15        ch=getchar();16    }17    return x*f;18 }19 struct node20 {21     int u,v,w;22     node(){}23     node(int vv,int ww)24     {25         v=vv,w=ww;26     }27 }g[100010];28 bool cmp(node a,node b)29 {30     return a.w
      
       >n>>p;52     init();53     int minc=0x3f3f3f3f;54     for(int i=1;i<=n;i++)55     {56         c[i]=read();57         minc=min(minc,c[i]); 58     } 59     for(int i=1;i<=p;i++)60         g[i].u=read(),g[i].v=read(),g[i].w=read()*2+c[g[i].u]+c[g[i].v];61     sort(g+1,g+1+p,cmp);62     int cnt=0;63     int total=0;64     for(int i=1;i<=p;i++)65     {66         if(merge(g[i].u,g[i].v))67         {68             cnt++;69             total+=g[i].w;70         }71     }72     cout<
       
        <