public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        int numberOfTest = scanner.nextInt();

        for (int test = 0; test < numberOfTest; ++test) {
            scanner.next();

            keysNumber = scanner.nextInt();
            int n = keysNumber + 1;
            costArray = new int[n][n];
            weightsArray = new int[n][n];
            nodesArray = new int[n][n];
            p = new int[n];
            q = new int[n];
            keysNames = new String[n];
            resultTree = new ArrayList<>();

            q[0] = scanner.nextInt();
            scanner.nextLine();

            for (int i = 1; i <= keysNumber; i++) {
                keysNames[i] = scanner.next();
                p[i] = scanner.nextInt();
                q[i] = scanner.nextInt();
                scanner.nextLine();
            }

            computeAllArrays();
            BST();
            rootGlobal = ConstructBST(0, keysNumber);
            CalculateDisplay(rootGlobal, 0);
            Collections.reverse(resultTree);
            displayResultTree();
            System.out.format(Locale.ENGLISH, "%.4f%n", RESULT);

        }
    }