Delivery man P93428

A delivery man works on a city modelled as a graph with $n$ vertices and $m$ bidirectional edges with positive distances. The delivery man has to pick and deliver $k$ objects in order from 1 to $k$. For each object $z \in \{1, \dots, k\}$, he has this information:

• the vertex $p_z$ where the object must be picked;

• the vertex $d_z$ where the object must be delivered, with $d_z \ne p_z$;

• the order $o_z$ to deliver the object.

The set $\{o_z\}$ is a permutation of $\{1, \dots, k\}$. For instance, if $k = 3$, $o_1 = 3$, $o_2 = 1$ and $o_3 = 2$, then the objects must be delivered in this order: 2, 3 and 1. In this case, the delivery man has to pick object 1 and afterwards pick object 2. Then, he can decide to pick object 3, or alternatively to deliver object 2. If he decides to deliver object 2, then he has to pick object 3, and so on.

What is the minimum total time to deliver all the objects? The delivery man can choose where to begin and where to end his journey. Assume that the time to pick and deliver objects is neglectable, and that the delivery man can carry as many objects as he wants.

Input

Input consists of several cases. Each case begins with $n$ and $m$, followed by $m$ triples $x$ $y$ $c$ indicating an edge between $x$ and $y$ with cost $c$, where $x \ne y$. Follow $k$, and the $k$ triples $p_z$ $d_z$ $o_z$ in order from 1 to $k$. Assume $2 \le n \le 1000$, $n - 1 \le m \le 5n$, that vertices are numbered starting at 0, $1 \le c \le 10^9$, that the graph is connected, that there is at most one edge between each pair of vertices, and $1 \le k \le 50$.

Output

For each case, print the minimum cost to deliver all the objects.