The first line in the input contains a single integer T, indicating the number of test cases ( 1T20 ) Each test case begins with five integers A, B, M, L and K - the number of Villages, the number of Castles (1A,B50), the number of roads, the maximal distance that can be covered at a time (1L500), and the number of times the boot can be used (0K10). The next M lines each contains three integers Xi,Yi, Li. That means there is a road connecting place Xi and Yi . The distance is Li, so the walk time is also Li(1Li100). Output For each test case in the input print a line containing a single integer indicating the minimal time needed to go home with the beautiful princess. It's guaranteed that Super Mario can always go home. Sample Input 1 42691 461 5610 455 354 234 123 Sample Output 9 interpret the input and explain how we get output=9 . explain line by line according to input