Description
My Legend is a facebook game developed by Happy Elements. It is a RPG game. You are the hero in that world, you will kill enemies and get items, money and experience points. You can level up and get higher ability points by accumulating of the experience points. You can also use the items dropped from the enemies to make better equipment. The money can buy items and upgrade the buildings. There is also a gem system. You can add the gems on your equipment to make them stronger.
This time a new update version is coming. You will get a sequence of items, and there will be some rules told you that if two kinds of the items are adjacent, they can become a new item. This new item could be the same with one of the original item. And each fusion will cost some money. Now given you the sequence of the items, you want to use the minimum cost to make the sequences of items in to only one item left. Please write a program to calculate the minimum cost.
For example, you get "ANT" "BEAR" "CAT" "CAT" this four items. And the following are the rules of fusion.
(a) ANT BEAR CAT 10
(b) CAT CAT CAT 15
The first rule means if "ANT" and "BEAR" are adjacent(no matter which one is on the left), they can become "CAT" using 10 dollars, and in this case, you want to make "CAT".
So a possible step will be
1. using rule (a) and pay 10 dollars to make the sequence become "CAT" "CAT" "CAT".
2. and using rule(b) two times with paying 15+15 dollars and you will get the goal.
The total cost of this case is 40.
Input
The first line of the input is an integer Z (1 ≤ Z ≤ 30), which means the number of test cases below.
The first line of each test case contains two integers N and M, where N is the length of the given sequence and M is the number of rules (1 ≤ N ≤ 50, 1 ≤ M ≤ K(K-1)/2).The following N lines describe the sequence. Each line contains a string represent the item's name. The length of the items' name are smaller than 10 and contains only capital English letters. And there are at most K kinds of items. (1 ≤ K ≤ 10) The following M lines describe the rules. Each line contains three strings and a integer V (1 ≤ V ≤ 105). It means if the first two kinds of item are adjacent, the can become the third item by using V dollars. The next line of the input is the kind of the item you want to get.
Output
For each test case, print an integer on a line which means the minimum number of dollars you need to pay to make the item you want. If there is no way to make the item you want, please print "IMPOSSIBLE" (without quote) on the line.