首先我们可以知道这道题中每个点只能经过一次，那么我们引入附加源汇source,sink，那么我们可以将每个点拆成两个点，分别表示对于图中这个节点我们的进和出，那么我们可以连接(source,i,1,0),(i+n,sink,1,0)，然后对于可以直接到达的点我们可以连接(source,i+n,1,cost)这个代表我们可以从任意一个点到达这个点，对于星球之间的连边我们可以连接(x,y+n,1,cost)，代表我们可以从这个星球到另一个星球，因为我们考虑每个点只经过一次，所以可以这样构图，我们并不关心路径的具体方案，只关心这个点会被进一次，出一次。

　

/**************************************************************    Problem: 1927    User: BLADEVIL    Language: C++    Result: Accepted    Time:2388 ms    Memory:1540 kb****************************************************************/ //By BLADEVIL#include 
     
      #include 
      
       #include 
       
        #define maxn 2010#define maxm 40010 using namespace std; int n,m,l,source,sink,ans;int last[maxn],pre[maxm],other[maxm],len[maxm],cost[maxm];int d[maxn],que[maxn*10],vis[maxn],father[maxn]; void connect(int a,int b,int c,int d){    pre[++l]=last[a];    last[a]=l;    other[l]=b;    len[l]=c;    cost[l]=d;    //if (c) printf("|%d %d %d\n",a,b,d);} bool spfa(){    memset(d,0x3f,sizeof d);    int h=0,t=1,cur;    que[1]=source; d[source]=0;    while (h
        
         d[cur]+cost[q])            {                father[other[q]]=q;                d[other[q]]=d[cur]+cost[q];                if (!vis[other[q]])                {                    que[++t]=other[q];                    vis[other[q]]=1;                }            }        }    }    return d[0]!=d[sink];} void update(){    int cur=sink,low=1<<30;    while (cur!=source)    {        low=min(low,len[father[cur]]);        cur=other[father[cur]^1];    }    cur=sink;    while (cur!=source)    {        ans+=cost[father[cur]];        len[father[cur]]-=low;        len[father[cur]^1]+=low;        cur=other[father[cur]^1];    }    //printf("%d\n",ans);} int main() {    scanf("%d%d",&n,&m);    source=(n<<1)+1; sink=source++; l=1;    for (int i=1;i<=n;i++) {        int x;        scanf("%d",&x);        connect(source,i+n,1,x); connect(i+n,source,0,-x);    }    for (int i=1;i<=n;i++)   connect(source,i,1,0),connect(i,source,0,0);    for (int i=1;i<=m;i++) {        int x,y,z;        scanf("%d%d%d",&x,&y,&z);        if (x>y) swap(x,y);        connect(x,y+n,1,z); connect(y+n,x,0,-z);    }    for (int i=1;i<=n;i++) connect(i+n,sink,1,0),connect(sink,i+n,0,0);    while (spfa()) update();    printf("%d\n",ans);    return 0;}