It's easy to think that the question is related to Steiner tree.

So let's suppose that f(i,sta)f(i,sta)f(i,sta) denotes the minimum cost when the root is iii and the state of pressure at the key point is sta stastasta.

Then all f(i,sta)f(i,sta)f(i,sta) can be found by using the template of Steiner tree.

Now consider how to meet the requirements of the topic.

Considering that the number of channels is also less than 101010, consider whether it can also be solved by using state pressure.

Let g(sta')g(sta') g(sta ') denote the minimum cost when the state of channel pressure is sta' sta 'sta'. (if the kkk bit under the binary system of sta'sta'sta'sta'is 111, it means that the key points of the kkk channel have been connected, otherwise they are not connected.).

Then let stap(i)stap(i)stap(i) STAP (I) denote the pressure state of all key points of the third channel (similar to sta sta sta in f(i,sta)f(i,sta)f(i,sta)).

Obviously, this thing can be preprocessed when it is read in.

Then let's talk about what I thought at the beginning:

For each channel I I I, set the value of G (1 < < I) g (1 < < I) g (1 < < I) to min (f(j,stapi))\min(f(j,stap_i))min(f(j,stapi​)). Then the other g()g()g() is set to inf ⁡ \ infinf.

Then enumerate the states of each sta'sta'sta ', update: g(sta') = min(g(s)+g(sta ′ - s))g(sta')=\min(g(s)+g(sta'-s))g(sta ') = min(g(s)+g(sta ′ - s)). (where sss is a subset of sta'sta'sta ')

But I found an important problem:

For example, in this figure, all nodes are key nodes. Points 111 and 444 are key nodes of channel 111, and points 222 and 333 are key nodes of channel 222. (the black number on the point represents the number of the point, the red number represents the channel to which the point belongs, and the number on the edge represents the weight of the edge.).

Obviously, g((1)2)=min ⁡ f(i,(1001)2)=w1+w2+w3g((1)_2)=\min f(i,(1001)_2)=w_1+w_2+w_3g((1)2​)=minf(i,(1001)2​)=w1​+w2​+w3​，g((10)2)=min⁡f(i,(0110)2)=w2g((10)_2)=\min f(i,(0110)_2)=w_2g((10)2​)=minf(i,(0110)2​)=w2​.

Then we can get: G (11) 2 = W1 + 2w2 + w3g (11)_ 2)=w_ 1+2w_ 2+w_ 3g((11)2​)=w1​+2w2​+w3​.

But obviously g((11)2)g((11)_2)g((11)2) should be equal to w1+w2+w3w_1+w_2+w_3w1​+w2​+w3​.

At this time, it will be found that dp will be the heavy edge.

How to solve it?

The solution I came up with:

When we started to initialize g() g(), we only initialized all G (1 < < I) g (1 < < I) g (1 < < I), and now we initialize every state of g() g().

That is to say, for each sta'sta'sta ', we use f()f()f() to initialize g(sta')g(sta ') g(sta').

The specific process can be seen in the code and implemented with dfs.

Finally, according to the original method, update: g(sta ') = min(g(s)+g(sta ′ - s))g(sta')=\min(g(s)+g(sta'-s))g(sta') = min(g(s)+g(sta ′ - s)). (where sss is a subset of sta'sta'sta ')

The code is as follows:

#include<bits/stdc++.h>

#define N 1010
#define M 3010

using namespace std;

int n,m,p,anssta,id[15],num[15],stap[15];
int cnt,head[N],w[M<<1],to[M<<1],nxt[M<<1];
int f[N][1025],g[1025];
bool inq[N];

//anssta is the pressure state of the answer (like sta)
//stap is the corresponding pressure state of each channel (like sta)

queue<int>q;

void adde(int u,int v,int wi)
{
	to[++cnt]=v;
	w[cnt]=wi;
	nxt[cnt]=head[u];
	head[u]=cnt;
}

void spfa(int sta)
{
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		inq[u]=false;
		for(int i=head[u];i;i=nxt[i])
		{
			int v=to[i];
			if(f[u][sta]+w[i]<f[v][sta])
			{
				f[v][sta]=f[u][sta]+w[i];
				if(!inq[v])
				{
					inq[v]=true;
					q.push(v);
				}
			}
		}
	}
}

void dfs(int k,int sum,int sump)
{
	if(k==p+1)
	{
		for(int i=1;i<=n;i++)
			g[sump]=min(g[sump],f[i][sum]);
		return;
	}
	dfs(k+1,sum|stap[k],sump|(1<<(k-1)));//Enumerate and select this channel (bit k of sta 'is 1)
	dfs(k+1,sum,sump);//Do not select this channel (the k-th bit of sta is 0)
}

int main()
{
	memset(f,0x3f,sizeof(f));
	memset(g,0x3f,sizeof(g));
	scanf("%d%d%d",&n,&m,&p);
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		adde(u,v,w),adde(v,u,w);
	}
	for(int i=1;i<=p;i++)
	{
		scanf("%d%d",&id[i],&num[i]);
		f[num[i]][1<<(i-1)]=0;
		stap[id[i]]|=(1<<(i-1));
		anssta|=(1<<(id[i]-1));
	}
	int maxn=(1<<p)-1;
	for(int sta=1;sta<=maxn;sta++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int now=sta;now;now=sta&(now-1))
				f[i][sta]=min(f[i][sta],f[i][now]+f[i][sta-now]);
			if(f[i][sta]!=0x3f3f3f3f)
			{
				q.push(i);
				inq[i]=true;
			}
		}
		spfa(sta);
	}
   //That's the template Steiner tree
	dfs(1,0,0);
	for(int sta=1;sta<=anssta;sta++)
		for(int now=sta;now;now=sta&(now-1))
			g[sta]=min(g[sta],g[now]+g[sta-now]);
	printf("%d\n",g[anssta]);
	return 0;
}