Untitled

import java.util.Scanner;

public class Main {
    public static void docProb(double[][] graph, int nodes, int time, int curNode, double p, double[] answer) {
        if (time <= 0) {
            answer[curNode] += p;
            return;
        }

        for (int i = 1; i <= nodes; i++) {
            if (graph[curNode][i] != 0) {
                p *= graph[curNode][i];
                docProb(graph, nodes, time - 10, i, p, answer);
                p /= graph[curNode][i];
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int nodes = sc.nextInt();
            int edges = sc.nextInt();
            int time = sc.nextInt();

            double[][] arr = new double[nodes + 1][nodes + 1];
            for (int i = 1; i <= nodes; i++) {
                for (int j = 1; j <= nodes; j++) {
                    arr[i][j] = 0;
                }
            }

            for (int i = 0; i < edges; i++) {
                int from = sc.nextInt();
                int to = sc.nextInt();
                double prob = sc.nextDouble();
                arr[from][to] = prob;
            }

            double[] answer = new double[nodes + 1];
            docProb(arr, nodes, time, 1, 1.0, answer);

            double finalProb = 0.0;
            int finalDivision = 0;

            for (int i = 1; i <= nodes; i++) {
                if (answer[i] > finalProb) {
                    finalProb = answer[i];
                    finalDivision = i;
                }
            }

            System.out.println(finalDivision);
        }
        sc.close();
    }
}