C++ の next_permutation を活用することで、 \(N\) 個の候補から \(K\) 個を取り出す行為を実装できます。
具体的には \(N-K\) 個の \(0\) 、 \(K\) 個の \(1\) をこの順に並べた列から始めて next_permutation を回すと所望の結果が得られます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int main(){
  ll N,M,K;
  cin >> N >> M >> K;
  vector<ll> A(N);
  for(auto &nx : A){cin >> nx;}
  vector<ll> U(M),V(M),B(M);
  for(ll i=0;i<M;i++){
    cin >> U[i] >> V[i] >> B[i];
    U[i]--; V[i]--;
  }
  vector<ll> fl(N,0);
  for(ll i=1;i<=K;i++){fl[N-i]=1;}
  ll best=-8e18;
  do{
    ll current=0;
    for(ll i=0;i<N;i++){
      if(fl[i]){current+=A[i];}
    }
    for(ll i=0;i<M;i++){
      if(fl[U[i]]>0 && fl[V[i]]>0){
        current-=B[i];
      }
    }
    best=max(best,current);
  }while(next_permutation(fl.begin(),fl.end()));
  cout << best << "\n";
  return 0;
}