#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<queue>

#define maxn 2005

#define maxm 200005

#define INF 0x3f3f3f3f

using namespace std;

inline int getint()

{

    int num=,flag=;char c;

    while((c=getchar())<''||c>'')if(c=='-')flag=-;

    while(c>=''&&c<='')num=num*+c-,c=getchar();

    return num*flag;

}

int n,m,Q;

int S,T;

int fir[maxn],nxt[maxm],to[maxm],cnt;

int cap[maxm],cst[maxm];

int dis[maxn];

int vis[maxn],pre[maxn];

int sum[maxn],tot;

int D[maxn][maxn];

inline void newnode(int u,int v,int w,long long c)

{to[++cnt]=v,nxt[cnt]=fir[u],fir[u]=cnt,cap[cnt]=w,cst[cnt]=c;}

inline void insert(int u,int v,int w,long long c)

{newnode(u,v,w,c),newnode(v,u,,-c);}

inline bool spfa()

{

    memset(dis,INF,sizeof dis);dis[S]=;

    memset(pre,-,sizeof pre);

    queue<int>Q;Q.push(S),vis[S]=;

    while(!Q.empty())

    {

        int u=Q.front();Q.pop();vis[u]=;

        for(int i=fir[u];i;i=nxt[i])

            if(cap[i]&&dis[to[i]]>dis[u]+cst[i])

            {

                dis[to[i]]=dis[u]+cst[i];pre[to[i]]=i^;

                if(!vis[to[i]])vis[to[i]]=,Q.push(to[i]);

            }

    }

    return ~pre[T];

}

inline int dinic()

{

    int num=;

    while(spfa())

    {

        tot++;

        sum[tot]=sum[tot-];

        int mn=INF;

        for(int i=pre[T];i!=-;i=pre[to[i]])mn=min(mn,cap[i^]);

        int tmp=;

        for(int i=pre[T];i!=-;i=pre[to[i]])cap[i]+=mn,cap[i^]-=mn,tmp+=cst[i^];

        sum[tot]+=tmp*mn,num+=mn;

    }

    return num;

}

int main()

{

    n=getint(),m=getint(),Q=getint();

    S=n*+,T=S+,cnt=;

    memset(D,INF,sizeof D);

    for(int i=;i<=n;i++)D[i][i]=;

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

    {

        int u=getint(),v=getint();

        D[u][v]=min(getint(),D[u][v]);

    }

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

        D[i][j]=min(D[i][j],D[i][k]+D[k][j]);

    for(int i=;i<=n;i++)insert(S,i,,),insert(i+n,T,,);

    for(int i=;i<=n;i++)for(int j=;j<=n;j++)if(i^j)insert(i,j+n,,D[i][j]);

    dinic();

    while(Q--)

    {

        int C=getint(),l=,r=tot,ans=;

        while(l<=r)

        {

            int mid=(l+r)>>;

            if(sum[mid]-sum[mid-]<C)l=mid+,ans=mid;

            else r=mid-;

        }

        printf("%d\n",sum[ans]+(n-ans)*C);

    }

}