IPC Latex

All submissions for this problem are available.
Allen Rusk is building Latex. Latex is a modern typesetting software which will be known for its letter AI. Note that Latex is a modern software and supports way more than 26 letters. The letter AI consists of a database of letter pairs with a hitrate and type associated with every pair. Since Latex is in beta stage, there are only two types of letter pairs right now: Modern and Rustic.
Today Allen is testing Latex.
Each test starts with a TestSum TS set to 0 and TypeSum PS set to 0. The test consists of N phases where N is the total number of distinct letters available to him. For the first phase he chooses a random letter and writes it down. For each subsequent phase, he chooses a letter R which has not been written down and also that there exists a letter L which has been written down and the letter pair L R exists in the AI database. He also adds the hitrate of L  R to his TestSum TS. Also, if the letter pair is Modern, he adds 1 to his TypeSum.
At the end of each test he checks his TypeSum. X is his lucky number. Hence if the TypeSum is equal to X or N  1  X, he notes down the TestSum for this test.
Allen doesn't have much to do today, and he spends the whole day testing Latex. So much so that he exhausts all tests that are possible with the given Letter AI database. Finally, he finds out the minimum among all the TestSums he noted in the entire day. However, this has been tiring for him and he wonders whether he can find out the Minimum TestSum given just the AI database. Can you?
Input
 First line containts a single integer T denoting the number of test cases. The description of T test cases follows.
 First line of each test case consists of 4 space separated integers N, M_{1}, M_{2}, X where N is the no. of distinct letters, M_{1} is the no.of pairs in AI database with type as Modern, M_{2} is the no. of pairs in AI database with type as Rustic and X is the lucky number.
 Next M_{1} lines for Modern type contains 3 space separated integers L, R, H denoting that pair L, R have type modern and hit rate H
 Next M_{2} lines for Rustic type contains 3 space separated integers L, R, H denoting that pair L, R have type rustic and hit rate H
 For each test case, output a single line containing the minimum test sum TS that he obtained with type sum equal to X or N  1  X. If there doesn't exist any such test print 1
 1 ≤ T ≤ 50
 1 ≤ N ≤ 200
 1 ≤ M_{1} + M_{2} ≤ 600
 0 ≤ X ≤ N  1
 1 ≤ L, R ≤ N
 1 ≤ H ≤ 100
Output
Constraints
Sample Input: 1 5 3 2 1 1 2 1 2 3 1 3 4 1 4 5 1 3 5 1 Sample Output: 4
Author:  ashish1610 
Tags  ashish1610 
Date Added:  1022016 
Time Limit:  1.5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions