#include<bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; using mint=modint998244353; //1000000007; using ll=long long; using pp=pair<int,int>; #define sr string #define vc vector #define fi first #define se second #define rep(i,n) for(int i=0;i<(int)n;i++) #define pb push_back #define all(v) v.begin(),v.end() #define pque priority_queue #define bpc(a) __builtin_popcount(a) int main(){ int n,m,kk;cin>>n>>m>>kk; vc d(n,vc<ll>(n,1e18)); vc<ll>x(n); rep(i,n)cin>>x[i]; rep(i,m){ int a,b,c;cin>>a>>b>>c; a--;b--; d[a][b]=c; d[b][a]=c; } rep(i,n)rep(j,n)rep(k,n)d[j][k]=min(d[j][k],d[j][i]+d[i][k]); vc dp(n,vc<ll>(1<<n,1e18)); rep(i,n)dp[i][1<<i]=x[i]; rep(i,1<<n)rep(j,n){ rep(k,n)if(~i>>k&1){ dp[k][i|1<<k]=min(dp[k][i|1<<k],dp[j][i]+x[k]+d[j][k]); } } ll ans=1e18; rep(i,1<<n)if(bpc(i)==kk)rep(j,n)ans=min(ans,dp[j][i]); cout<<ans; }