Input 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 1445432126655326110544391 Sample Output 9 Interpret input line by line. how calculate this output =9. solve step by step by using input values and find output