#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
typedef long long ll;
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REP(i,num,n) for(int i=num, i##_len=(n); i<i##_len; ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define print(x) (cout << (x) << endl)
#define pb push_back
#define mp make_pair
#define sz(x) int(x.size())
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class itr> void cins(itr first, itr last){ for(auto i = first; i != last; i++){ cin >> (*i); } }
template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++) ans += to_string(*i) + " "; if(!ans.empty()) ans.pop_back(); cout << ans << endl; }
#define fs first
#define sc second

const int INF = 1e9;
const ll LLINF = 1e16;
const ll MOD = 1e9+7;
template<class T> inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;};

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}
 
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
 

// 指定した文字cが文字列に何文字入ってるか
ll stringcount(string s, char c) {
    return count(s.cbegin(), s.cend(), c);
}


// 割り算の切り上げ処理
template<typename T>
T rp(T a, T b) {
  return (a + b - 1) / b;
}

// 桁和
template<typename T>
T digsum(T n) {
    T res = 0;
    while(n > 0) {
        res += n%10;
        n /= 10;
    }
    return res;
}

// 回文判定
bool kai (string s) {
    string t{s};
    reverse(begin(t), end(t));
    return s == t;
}

using pint = pair<int, int>;
using pll = pair<ll, ll>;



int main(void)
{
    cout.tie(0);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    ll a,b,m;
    cin >> a >> b >> m;
    vector<ll> A(a);
    vector<ll> B(b);
    cins(all(A));
    cins(all(B));
    ll ma = *min_element(all(A));
    ll mb = *min_element(all(B));
    ll ans = ma + mb;
    rep(i, m){
        ll x,y,c;
        cin >> x >> y >> c;
        --x, --y;
        chmin(ans, A[x] + B[y] - c);
    }
    print(ans);


}


#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define poly vector<ll>
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define For(i,l,r) for(int i=(int)(l);i<=(int)(r);i++)
#define Rep(i,r,l) for(int i=(int)(r);i>=(int)(l);i--)
inline ll read(){
	ll x=0;char ch=getchar();bool d=1;
	for(;!isdigit(ch);ch=getchar()) if(ch=='-') d=0;
	for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
	return d?x:-x;
}
inline void write(ll x){
	if(x<0) x=-x,putchar('-');
	if(x>=10) write(x/10);
	putchar('0'+x%10);
}
inline void writeln(ll x){write(x);puts("");}
inline void writep(ll x){write(x);putchar(' ');}
inline ull rnd(){
	return ((ull)rand()<<30^rand())<<4|rand()%4;
}
const int N=20,M=(1<<15)+5;
ll f[M][N],g[M];
vector<pii> v[N];
void upd(ll &x,ll y){
	x=max(x,y);
}
int main(){
	int n=read(),m=read();ll tot=0;
	For(i,1,m){
		int x=read(),y=read(),z=read();tot+=z;
		v[x].pb(mp(y,z));v[y].pb(mp(x,z));
	}
	int st=(1<<n)-1;
	For(s,0,st){
		For(i,1,n) if(!(s>>(i-1)&1)){
			if(!g[s|(1<<(i-1))]){
				g[s|(1<<(i-1))]=g[s];
				for(auto x:v[i]){
					if(s>>(x.fi-1)&1){
						g[s|(1<<(i-1))]+=x.se;
					}
				}
			}
		}
	}
	memset(f,-1,sizeof(f));
	f[1][1]=0;
	For(s,1,st){
		For(i,1,n) if(s>>(i-1)&1){
			if(f[s][i]==-1) continue;
			for(auto x:v[i]){
				if(!(s>>(x.fi-1)&1)){
					upd(f[s|(1<<(x.fi-1))][x.fi],f[s][i]+x.se);
				}
			}
			int ss=(st^s)|(1<<(i-1));
			for(int t=ss;t;t=(t-1)&ss){
				if(t>>(i-1)&1){
					upd(f[s|t][i],f[s][i]+g[t]);
				}
			}
		}
	}
	cout<<tot-f[st][n];
}