hdu3311

#include <bits/stdc++.h>

using namespace std;

#define maxn 10000

#define INF 6e8

bool inq[];

int dp[][],v[];

struct re{

    int a,b,c;

}a[maxn];

int l,n,m,p,head[],dis[][];

void arr(int x,int y,int z)

{

    a[++l].a=head[x];

    a[l].b=y;

    a[l].c=z;

    head[x]=l;

}

void spfa()

{

    queue<int> q;

    for (int s=;s<=n+m;s++)

    {

        for (int j=;j<=n+m;j++)

          dis[s][j]=INF;

        dis[s][s]=;

        q.push(s); inq[s]=;

        while (!q.empty())

        {

            int x=q.front(); q.pop();

            int u=head[x];

            while (u)

            {

                int v=a[u].b;

                if (dis[s][v]>dis[s][x]+a[u].c)

                {

                    dis[s][v]=dis[s][x]+a[u].c;

                    if (!inq[v])

                    {

                          q.push(v); inq[v]=;

                    }

                }

                u=a[u].a;

            }

            inq[x]=;

        }

    }

}

void get_ans()

{

    for (int i=;i<=(<<n)-;i++)

      for (int j=;j<=n+m;j++)

        dp[i][j]=INF;

    for (int i=;i<=n;i++)

      dp[<<(i-)][i]=;

    for (int i=;i<=(<<n)-;i++)

     {

      for (int j=;j<=n+m;j++)

      {

           for (int k=i;k;k=(k-)&i)

             if (dp[i][j]>dp[k][j]+dp[i^k][j])

               dp[i][j]=dp[k][j]+dp[i^k][j];

      }   for (int k1=;k1<=n+m;k1++)

           for (int k2=;k2<=n+m;k2++)

             if (dp[i][k1]>dp[i][k2]+dis[k2][k1])

               dp[i][k1]=dp[i][k2]+dis[k2][k1];

}

}

int main()

{

    freopen("noip.in","r",stdin);

    std::ios::sync_with_stdio(false);

    while (cin>>n>>m>>p&&n>)

    {

        l=;memset(head,,sizeof(head));

        for (int i=;i<=m+n;i++)

        {

          cin>>v[i];

          arr(i,,v[i]);

        }

        int c,d,e;

        for (int i=;i<=p;i++)

        {

            cin>>c>>d>>e;

            arr(c,d,e); arr(d,c,e);

        }

        spfa();

        get_ans();

        cout<<dp[(<<n)-][]<<endl;

    }

    return ;

}