#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<assert.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define INF 1000000001

typedef struct struct_listgraphintcostintflow{
  int node, nodeMemory;
  int *edgeSize, *edgeMemory;
  int **edge, **cost, **flow, **reverse;
} ListGraphIntCostIntFlow;

ListGraphIntCostIntFlow NewListGraphIntCostIntFlow(int maxNode,int maxDegree){
  int i; ListGraphIntCostIntFlow res;
  res.node=0; res.nodeMemory=maxNode;
  res.edgeSize   = (int*)malloc(maxNode*sizeof(int));
  res.edgeMemory = (int*)malloc(maxNode*sizeof(int));
  res.edge = (int**)malloc(maxNode*sizeof(int*));
  res.cost = (int**)malloc(maxNode*sizeof(int*));
  res.flow = (int**)malloc(maxNode*sizeof(int*));
  res.reverse = (int**)malloc(maxNode*sizeof(int*));
  if(maxDegree){
    rep(i,maxNode) res.edge[i]=(int*)malloc(maxDegree*sizeof(int));
    rep(i,maxNode) res.cost[i]=(int*)malloc(maxDegree*sizeof(int));
    rep(i,maxNode) res.flow[i]=(int*)malloc(maxDegree*sizeof(int));
    rep(i,maxNode) res.reverse[i]=(int*)malloc(maxDegree*sizeof(int));
  }
  rep(i,maxNode) res.edgeMemory[i]=maxDegree;
  return res;
}

void DeleteListGraphIntCostIntFlow(ListGraphIntCostIntFlow g){
  int i;
  rep(i,g.nodeMemory) if(g.edgeMemory[i]){free(g.edge[i]); free(g.cost[i]); free(g.flow[i]); free(g.reverse[i]);}
  free(g.edgeSize); free(g.edgeMemory); free(g.edge); free(g.cost);
}

void ListGraphIntCostIntFlowSetEmpty(ListGraphIntCostIntFlow *g,int node){
  int i;
  g->node = node;
  rep(i,node) g->edgeSize[i]=0;
}

void ListGraphIntCostIntFlowOneEdgeReallocEasy(ListGraphIntCostIntFlow *g,int k,int size,int fg){
  if(fg==1 && g->edgeMemory[k]>=size) return;
  if(g->edgeMemory[k]==size) return;
  if(g->edgeMemory[k]){free(g->edge[k]); free(g->cost[k]); free(g->flow[k]); free(g->reverse[k]);}
  g->edgeMemory[k]=size;
  g->edge[k] = (int*)malloc(size*sizeof(int));
  g->cost[k] = (int*)malloc(size*sizeof(int));
  g->flow[k] = (int*)malloc(size*sizeof(int));
  g->reverse[k] = (int*)malloc(size*sizeof(int));
}

void ListGraphIntCostIntFlowAddEdge(ListGraphIntCostIntFlow *g,int node1,int node2,int cost,int flow){
  int s1,s2;
  s1=g->edgeSize[node1]++, s2=g->edgeSize[node2]++;
  g->edge[node1][s1]=node2; g->cost[node1][s1]= cost; g->flow[node1][s1]=flow; g->reverse[node1][s1]=s2;
  g->edge[node2][s2]=node1; g->cost[node2][s2]=-cost; g->flow[node2][s2]=0;    g->reverse[node2][s2]=s1;
}



void intHeapGoUp(int n,int hp[],int hpi[],int d[]){
  int k,m;
  if(!n) return;
  m=(n-1)/2;
  if(d[hp[m]]<=d[hp[n]]) return;
  k=hp[m]; hp[m]=hp[n]; hp[n]=k;
  hpi[hp[m]]=m; hpi[hp[n]]=n;
  intHeapGoUp(m,hp,hpi,d);
}

void intHeapGoDown(int n,int hp[],int hpi[],int hp_size,int d[]){
  int k,m;
  m=2*n+1; if(m>=hp_size) return;
  if(hp_size>m+1 && d[hp[m]]>d[hp[m+1]]) m++;
  if(d[hp[m]]>=d[hp[n]]) return;
  k=hp[m]; hp[m]=hp[n]; hp[n]=k;
  hpi[hp[m]]=m; hpi[hp[n]]=n;
  intHeapGoDown(m,hp,hpi,hp_size,d);
}

void intHeapInsert(int n,int hp[],int hpi[],int *hp_size,int d[]){
  hp[*hp_size]=n; hpi[n]=(*hp_size)++;
  intHeapGoUp((*hp_size)-1,hp,hpi,d);
}

int intHeapDelete(int hp[],int hpi[],int *hp_size,int d[]){
  int r=hp[0]; hpi[r]=-1;
  if( *hp_size==1 ){(*hp_size)--; return r;}
  hp[0]=hp[--(*hp_size)]; hpi[hp[0]]=0;
  intHeapGoDown(0,hp,hpi,*hp_size,d);
  return r;
}


/* INF=1000000000=unreachable */
/* 負の閉路がなければ負枝があってもよい．が，その場合ed=-1と指定すること． */
/* flowが流れることができる枝のみを考えてダイクストラするんだ． */
void ListGraphIntCostIntFlowDijkstra(ListGraphIntCostIntFlow g,int st,int ed,int res_dist[],int res_back_node[],int res_back_edge[],void *WorkMemory){
  int i,j,k,n=g.node,hp_size=0; int c;
  int *hp, *hpi;

  hp  = (int*) WorkMemory; WorkMemory = (void*)( hp  + n );
  hpi = (int*) WorkMemory; WorkMemory = (void*)( hpi + n );

  rep(i,n) hpi[i]=-1, res_dist[i]=1000000000, res_back_node[i]=-1; res_dist[st]=0;
  intHeapInsert(st,hp,hpi,&hp_size,res_dist);
  while(hp_size){
    i = intHeapDelete(hp,hpi,&hp_size,res_dist);
    if(i==ed) break;
    rep(j,g.edgeSize[i]) if(g.flow[i][j]>0) {
      k=g.edge[i][j]; c=res_dist[i]+g.cost[i][j];
      if(res_dist[k] <= c) continue; res_dist[k]=c; res_back_node[k]=i; res_back_edge[k]=j;
      if(hpi[k]<0) intHeapInsert(k,hp,hpi,&hp_size,res_dist);
      else         intHeapGoUp(hpi[k],hp,hpi,res_dist);
    }
  }
}


int flow_cost[1000], flow_size;

void ListGraphIntCostIntFlowMinCostFlow(ListGraphIntCostIntFlow g,int st,int ed,void *WorkMemory){
  int i,j,k,l,flow_max;
  int *dist, *back_node, *back_edge;

  dist = (int*) WorkMemory; WorkMemory = (void*) (dist + g.node);
  back_node = (int*) WorkMemory; WorkMemory = (void*) (back_node + g.node);
  back_edge = (int*) WorkMemory; WorkMemory = (void*) (back_edge + g.node);
  
  for(;;){
    ListGraphIntCostIntFlowDijkstra(g,st,-1,dist,back_node,back_edge,WorkMemory);
    if(back_node[ed]==-1) break;
    
    flow_max = 1;
    k=ed;
    while(back_node[k]!=-1){
      i=back_node[k]; j=back_edge[k]; l=g.reverse[i][j];
      g.flow[i][j] -= flow_max; g.flow[k][l] += flow_max;
      k=i;
    }
    flow_cost[flow_size++] = dist[ed];
  }
}

void intIntSort(int d[],int m[],int s){int i=-1,j=s,k,t;if(s<=1)return;k=(d[0]+d[s-1])/2;for(;;){while(d[++i]<k);while(d[--j]>k);if(i>=j)break;t=d[i];d[i]=d[j];d[j]=t;t=m[i];m[i]=m[j];m[j]=t;}intIntSort(d,m,i);intIntSort(d+j+1,m+j+1,s-j-1);}



int main(){
  int N, M, K, S[30100], T[30100], V[30100], C[110000], edge[251][251];
  static int q[110000], ind[110000], res[110000];
  int i, j, k;
  int flow, cost, n_flow, n_cost, f_st;

  ListGraphIntCostIntFlow g = NewListGraphIntCostIntFlow(600, 600);
  int node, st, ed;
  void *mem = malloc(10000000);

  assert( scanf("%d%d%d",&N,&M,&K)==3 );
  assert( 2<=N && N<=250 && 1<=M && M<=30000 && 1<=K && K<=10000);

  rep(i,M){
    assert( scanf("%d%d%d",S+i,T+i,V+i)==3 );
    assert( S[i]!=T[i] && 1<=S[i] && S[i]<=N && 1<=T[i] && T[i]<=N );
    S[i]--; T[i]--;
  }

  rep(i,K) assert( scanf("%d",C+i)==1 ), assert( 1<=C[i]&&C[i]<=10000 );

  rep(i,N) rep(j,N) edge[i][j] = INF;
  rep(i,N) edge[i][i] = 0;

  rep(i,M) if(edge[S[i]][T[i]] > V[i]) edge[S[i]][T[i]] = V[i];
  rep(k,N) rep(i,N) rep(j,N) if(edge[i][j] > edge[i][k]+edge[k][j]) edge[i][j] = edge[i][k]+edge[k][j];

  rep(i,K) q[i] = C[i], ind[i] = i;
  intIntSort(q,ind,K);

  node = 2*N; st = node++; ed = node++;
  ListGraphIntCostIntFlowSetEmpty(&g, node);
  rep(i,N) ListGraphIntCostIntFlowAddEdge(&g, st, i, 0, 1);
  rep(i,N) ListGraphIntCostIntFlowAddEdge(&g, i+N, ed, 0, 1);
  rep(i,N) rep(j,N) if(i!=j && edge[i][j] < INF) ListGraphIntCostIntFlowAddEdge(&g, i, j+N, edge[i][j], 1);

  flow_size = 0;
  ListGraphIntCostIntFlowMinCostFlow(g,st,ed,mem);

  flow = cost = 0;
  rep(k,K){
    while(flow < flow_size && flow_cost[flow] < q[k])
      cost += flow_cost[flow++];
    res[ind[k]] = q[k] * (N-flow) + cost;
  }

  rep(i,K) printf("%d\n",res[i]);
  
  return 0;
}