Problem

You have recently joined the HR department of a mid-size startup in Bangalore. The startup operates smoothly through the coordinated efforts of multiple departments such as Sales, Marketing, Tech, Accounts, etc. all under the same roof. Communication between these various departments is a crucial task that must be handled by the HR department.

You are provided with details about the communication pathways between departments. If department i and department j need to communicate for a meeting or collaboration, department i can directly reach out to department j to set it up, or vice versa. In doing so, a certain amount of time, t time units, is expended in the communication process. However, due to the hierarchical structure of communication between departments, not all departments can communicate directly with each other. Sometimes, department i may have to communicate with department j via several intermediary departments. In these cases, the time taken for communication increases as the messages pass through each department in the chain, adding up the time units and causing delays.

To ensure efficient communication, the HR department decides to implement a time_cutoff to analyze the time spent on inter-departmental communication. If the time required for communication between two departments exceeds (strictly greater than) the time_cutoff it is not considered when evaluating which department is the best at communicating with others. The department deemed best at communication is the one that, within the time_cutoff, can communicate with the most other departments, with the fewest time units spent.

Note: Give priority to connections with most departments first, then fewest time units, then department number.

Input

The first line of input contains one integer t, the number of test cases.

The input of each testcase is as follows:

The first line contains three space-separated integers, n, m, and time_cutoff where n is the number of departments at your company and m is the number of direct communications between these departments.

The next m lines each contain three space-separated integers i, j, and t where i and j are the department numbers and t is the time taken for direct communication between these departments.

Constraints

• 1 ≤ t ≤ 50
• 2 ≤ n ≤ 100
• 0 ≤ i, j ≤ n-1
• 1 ≤ m ≤ n*(n-1)/2
• 1 ≤ t, time_cutoff ≤ 10⁴

Output

For each test case, print one integer, the department number which can communicate with the most departments within the time_cutoff and in the fewest time units spent. In case of a tie, return the department with the higher department number.

Example

Input:

2
4 4 4
0 1 3
1 2 1
1 3 4
2 3 1
4 4 5
0 1 1
1 2 4
2 3 1
0 3 3
    

Output:

2
3
    

Explanation

For testcase 1, the below-stated diagram is the department connection structure. When analyzing the best department, department 1 has communication with 3 other departments within the time cutoff so does department 2. They both equally spend 6 total time units in doing so. To break the tie we return the department with the higher department number which is department 2.

For testcase 2, the below-stated diagram is the department connection structure. When analyzing the best department, all departments can communicate with all other departments within the time cutoff. Department 0 and 3 have the least total time of communication of 8 units of time. To break the tie we return the department with the higher department number which is department 3.

Solution

import heapq  # Importing the heapq module to use the priority queue (min-heap)
from collections import defaultdict  # Importing defaultdict for easy dictionary creation

# Function to implement Dijkstra's algorithm for finding the shortest paths
def dijkstra(n, graph, start, time_cutoff):
    # Initialize distance dictionary with infinity for all nodes
    dist = {i: float('inf') for i in range(n)}
    dist[start] = 0  # Distance to the start node is 0
    
    # Initialize the priority queue with the start node
    heap = [(0, start)]
    
    while heap:  # While there are nodes to process
        current_dist, node = heapq.heappop(heap)  # Get the node with the smallest distance
        
        # If this distance is already larger than the known distance, skip it
        if current_dist > dist[node]:
            continue
        
        # Explore neighbors of the current node
        for neighbor, time in graph[node]:
            distance = current_dist + time  # Calculate new distance to neighbor
            if distance < dist[neighbor]:  # If the new distance is shorter
                dist[neighbor] = distance  # Update the shortest distance
                heapq.heappush(heap, (distance, neighbor))  # Add the neighbor to the heap
    
    # Calculate how many nodes are reachable within the time_cutoff
    reachable = 0
    total_time = 0
    for d in dist.values():
        if d <= time_cutoff:  # Only consider nodes within the time_cutoff
            reachable += 1
            total_time += d  # Sum the total time spent communicating
    
    return reachable, total_time  # Return the number of reachable nodes and total communication time

# Function to find the best department for communication
def find_best_department(n, m, time_cutoff, connections):
    # Create an adjacency list to represent the graph
    graph = defaultdict(list)
    for i, j, t in connections:
        graph[i].append((j, t))  # Add edge from i to j with time t
        graph[j].append((i, t))  # Add edge from j to i with time t (because the graph is undirected)
    
    best_department = -1  # Initialize the best department
    max_reachable = -1  # Initialize the max number of reachable departments
    min_time = float('inf')  # Initialize the minimum time spent
    
    # Check each department to see if it is the best for communication
    for department in range(n):
        reachable, total_time = dijkstra(n, graph, department, time_cutoff)  # Run Dijkstra's algorithm
        
        # Update the best department based on the problem's criteria
        if (reachable > max_reachable) or \
           (reachable == max_reachable and total_time < min_time) or \
           (reachable == max_reachable and total_time == min_time and department > best_department):
            best_department = department  # Update to the current department
            max_reachable = reachable  # Update the max number of reachable departments
            min_time = total_time  # Update the minimum time spent
    
    return best_department  # Return the best department

# Main function to handle input and output
def main():
    t = int(input().strip())  # Read the number of test cases
    results = []  # List to store results for each test case
    for _ in range(t):
        n, m, time_cutoff = map(int, input().strip().split())  # Read n, m, and time_cutoff
        connections = []
        for _ in range(m):
            i, j, t = map(int, input().strip().split())  # Read each connection
            connections.append((i, j, t))  # Store the connection
        result = find_best_department(n, m, time_cutoff, connections)  # Find the best department
        results.append(result)  # Store the result
    
    for result in results:  # Output all results
        print(result)

if __name__ == "__main__":
    main()  # Run the main function when the script is executed

Explanation

The given problem can be solved using Dijkstra's algorithm to find the shortest paths from a source node to all other nodes in the graph. The algorithm is implemented in the dijkstra function, which takes the number of nodes, the graph representation, the starting node, and the time cutoff as input. It returns the number of reachable nodes within the time cutoff and the total time spent communicating with them.

The find_best_department function creates an adjacency list representation of the graph based on the input connections. It then iterates over each department to find the best department for communication. The best department is determined based on the number of reachable departments, the total time spent communicating, and the department number in case of a tie.

The main function reads the input, processes each test case, and outputs the best department for communication in each case.

Complexity Analysis

Let n be the number of departments and m be the number of direct communications between departments.

The time complexity of the Dijkstra's algorithm implementation is O(n log n + m) for each test case. The find_best_department function iterates over all departments, running Dijkstra's algorithm for each, resulting in a total time complexity of O(n² log n + n*m) for each test case.

Therefore, the overall time complexity of the solution is O(t * (n² log n + n*m)) for t test cases.

The space complexity of the solution is O(n + m) to store the graph representation and the results for each test case.

Sample Solution Provided by Instructor