The Pope has commissioned the Holy Roman Empire, ruled by ruthless King Frederick Barbarossa (Red Beard), and England, lead by brave King Richard the Lionheart, to recover the holy land of Jerusalem from the moors. Both commanders know very well their armies cannot meet on a road, or a quarrel may break out. They therefore wish to take different paths to get to Jerusalem, which means no road will be chosen by both king for their troops to march by. Soldiers from both bands may meet at towns and cities, however, where they will probably not mind each other. There is another difficulty: some paths are narrow and a limited number of soldiers can march across them. To deal with this problem, both commanders are willing to divide their troops into as many groups as it is needed in order to ensure that the greatest number of soldiers (no matter which kingdom they belong to) will arrive at Jerusalem to fight the moors. Given a map of towns and cities connected by roads which can admit a certain number of soldiers and the initial position of King Frederick’s and King Richard’s troops (which are always different), your task is to determine the largest number of soldiers that can get to Jerusalem. Input The first line of input contains the number t of test cases (1 ≤ t ≤ 60). Each test case will begin with a line containing integers N and M (5 ≤ N ≤ 12 and 5 ≤ M ≤ 30) corresponding to the number of towns and the number of roads in the map. Towns will be numbered from 1 to N. M lines follow, each containing integers A, B and C (1 ≤ A, B ≤ N and 1 ≤ C ≤ 100), indicating that there is a two-way road from town A to town B by which at most C soldiers can march. The last line of each case will contain integers F, R and J (1 ≤ F,R,J ≤ N) corresponding to the initial locations of Frederick’s army, Richard’s army and Jerusalem, which will always be different. Output For each test case print on a separate line the largest number of soldiers that can get to Jerusalem.
2/2 Sample Input 2 66 1 3 10 235 3 4 11 3 5 11 4 6 11 562 126 56 159 1 3 10 3 2 10 349 3 5 10 5 4 100 124 Sample Output 12 28