Tourist Attractions

Byteasar travels from Bitingham to Byteburg. Along the way he wants to visit some must-see sites, including interesting monuments, fine restaurants, and numerous other tourist attractions. The order in which he visits the places is not entirely unimportant. For example, Byteasar would rather not climb the peaky tower of Bitfork Castle right after a lavish dinner in Digitest, and likewise he would drop in to Zip City (called by some Sip City) for a cup of the famous Compresso coffee after dinner rather than before. Luckily his tour is, to some extent, flexible, and he can choose between several orders. Because of horrendous petrol prices, he would like to follow the shortest possible route, for economy's sake. Be a good friend and help him determine the length of the shortest route that meets his requirements.

The road network consists of $n$ sites and $m$ roads connecting them. The sites are numbered from $1$ to $n$, and so are the roads (from $1$ to $m$). Each road links a pair of different sites, is bidirectional, and has a certain length. Different roads meet only at sites (their endpoints) and do not cross outside the sites, thanks to a clever system of flyovers and tunnels. A pair of sites can be connected directly by at most one road, though there can be many paths consisting of at least two direct roads between them.

Let $k$ denote the number of sites Byteasar wants to visit. Bitingham has number $1$, Byteburg has number $n$, and the sites Byteasar wants to visit have numbers $2, 3, \dots, k+1$.

An example road network is shown in the figure. Suppose Byteasar wants to visit sites $2, 3, 4$ and $5$, and he would like to visit $2$ before $3$, and $4$ and $5$ after $3$. Then the shortest route leads through sites $1, 2, 4, 3, 4, 5, 8$ and its length is $19$.

Note that site $4$ appears on the route both before and after site $3$. This is perfectly fine and means that Byteasar will not stop there before visiting site $3$, since his requirements disallow it. He is, however, allowed to pass through site $4$ without stopping before visiting site $3$, and this is exactly what he is going to do.

Write a program that:

• reads from standard input the description of the road network, the list of sites Byteasar has chosen to visit, and the restrictions on the order in which he wants to visit them,
• determines the length of the shortest route leading in an appropriate order through all the chosen sites,
• writes the result to standard output.

The first line of standard input contains three integers $n$, $m$ and $k$, separated by single spaces, with $2 \le n \le 20{,}000$, $1 \le m \le 200{,}000$, $0 \le k \le 20$; furthermore, $k \le n - 2$ holds.

The following $m$ lines contain the descriptions of the roads, exactly one per line. The $(i+1)$-th line contains three integers $p_i$, $q_i$ and $l_i$, separated by single spaces, with $1 \le p_i < q_i \le n$ and $1 \le l_i \le 1{,}000$. These numbers denote a road linking sites $p_i$ and $q_i$ of length $l_i$. You may assume that for each test case it is possible to travel from Bitingham to Byteburg and to each of the sites Byteasar wants to visit.

The $(m+1)$-th line contains one integer $g$ ($0 \le g \le k \cdot (k-1) / 2$). It is the number of restrictions on the order in which Byteasar wants to visit the sites of his selection. These restrictions are given in the following $g$ lines, one per line. The $(m+i+1)$-th line contains two integers $r_i$ and $s_i$ separated by a single space, with $2 \le r_i \le k+1$, $2 \le s_i \le k+1$, $r_i \ne s_i$. The pair $(r_i, s_i)$ means that Byteasar wants to visit site $r_i$ before visiting site $s_i$. It does not, however, prevent him from passing through $s_i$ before visiting $r_i$, nor from passing through $r_i$ after having visited $s_i$; he is free to do so as long as he does not stop and visit the tourist attractions. It is guaranteed that for each test case at least one order of visiting the selected sites that satisfies all the restrictions exists.

Output a single integer: the length of the shortest route from Bitingham to Byteburg that passes, in a proper order, through all the sites Byteasar has selected.