In a word, it is necessary to make the minimum path coverage. As long as the path is not a ring with a length greater than 1, it needs to pay the additional cost of C. Give C many times to find the answer. n≤250,m≤30000,q≤104n\le250,m\le30000,q\le10^4n≤250,m≤30000,q≤104
Solution: consider how to fix C. Considering the process of undirected graph minimum path coverage, we can either merge two paths at a time, and pay less one C, or form a ring, or pay less one C. So the minimum path coverage gain per augmentation is cost-C (initially nC). As for how to do the minimum path coverage, we notice that we can do the minimum chain coverage directly after finding the transitive closure. As for how to do this, please Baidu (escape).
Then each time I ask, I will obviously choose the cost of cost < C to expand, just two points.

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define Rep(i,v) rep(i,0,(int)v.size()-1)
#define lint long long
#define ull unsigned lint
#define db long double
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define gc getchar()
#define debug(x) cerr<<#x<<"="<<x
#define sp <<" "
#define ln <<endl
using namespace std;
typedef pair<int,int> pii;
typedef set<int>::iterator sit;
inline int inn()
{
	int x,ch;while((ch=gc)<'0'||ch>'9');
	x=ch^'0';while((ch=gc)>='0'&&ch<='9')
		x=(x<<1)+(x<<3)+(ch^'0');return x;
}
const int N=510,M=3000010,INF=1000000000;
struct edges{
	int from,to,pre,resf,cost;
}e[M];int h[N],etop,g[N][N],x[N],y[N],d[N],inq[N],fr[N],lstc;queue<int> q;pii lst[N];
inline int add_edge(int u,int v,int f,int c) { int x=++etop;return e[x].from=u,e[x].to=v,e[x].pre=h[u],h[u]=x,e[x].resf=f,e[x].cost=c; }
inline int build_edge(int u,int v,int f,int c) { return add_edge(u,v,f,c),add_edge(v,u,0,-c); }
inline int spfa(int s,int t)
{
	rep(i,1,t) d[i]=INF,inq[i]=fr[i]=0;
	while(!q.empty()) q.pop();
	d[s]=0,inq[s]=1,q.push(s);
	while(!q.empty())
	{
		int x=q.front();q.pop(),inq[x]=0;
		for(int i=h[x],y;i;i=e[i].pre)
			if(e[i].resf&&d[y=e[i].to]>d[x]+e[i].cost)
				d[y]=d[x]+e[i].cost,fr[y]=i,(!inq[y]?inq[y]=1,q.push(y),0:0);
	}
	if(!fr[t]) return 0;
	for(int i=fr[t];i;i=fr[e[i].from])
		e[i].resf--,e[((i-1)^1)+1].resf++;
	return lst[++lstc]=mp(d[t],d[t]),1;
}
inline int min_cost(int s,int t) { while(spfa(s,t));return 0; }
inline int query(int n,int c)
{
	int L=1,R=lstc;
	while(L<=R)
	{
		int mid=(L+R)>>1;
		if(lst[mid].fir<c) L=mid+1;
		else R=mid-1;
	}
	return n*c-R*c+lst[R].sec;
}
int main()
{
	int n=inn(),m=inn(),q=inn(),u,v,cnt=0;
	rep(i,1,n) rep(j,1,n) g[i][j]=INF;rep(i,1,n) g[i][i]=0;
	rep(i,1,m) u=inn(),v=inn(),g[u][v]=min(g[u][v],inn());
	rep(k,1,n) rep(i,1,n) rep(j,1,n) g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
	rep(i,1,n) g[i][i]=INF,x[i]=++cnt,y[i]=++cnt;int s=++cnt,t=++cnt;
	rep(i,1,n) build_edge(s,x[i],1,0),build_edge(y[i],t,1,0);
	rep(i,1,n) rep(j,1,n) if(g[i][j]<INF) build_edge(x[i],y[j],1,g[i][j]);
	min_cost(s,t);rep(i,1,lstc) lst[i].sec+=lst[i-1].sec;
	while(q--) printf("%d\n",query(n,inn()));return 0;
}