Description
You are given a graph with n nodes, e edges. Each edge is represented as a triplet a, b, p, representing an undirected weighted edge connecting the nodes a and b with an integer weight w.
Given an upper bound on the path length (referred to as length limit hereafter) m, you are asked to find the node with the maximum number of reachable nodes in respect of m, where a node u is a reachable node in respect of m from v if and only if 1) there is a path p between u and v, and 2) the total edge weight on p does not exceed the length limit m (i.e. p<=m). If there are multiple nodes having the maximum number of reachable nodes, return the node with the largest index. After you find the node, you should also print out all the reachable nodes of this node.
Consider the graph above as an example. Assume the length limit is 5. Then, node 5 has the maximum number of reachable nodes, where path (1,5) has length 4; path (2,5) has length 4; path (3,5) has length 4, path (4,5) has length 3.
The answer is 5, and we also print out 1, 2, 3, 4 as its reachable nodes.
Note that all STL library are forbidden.
Each line of output should be followed by a newline character.
Input
The first line contains a pair of integers n and e, which are the numbers of nodes and edges, respectively.
The second line includes one integer m, i.e., the length limit.
The following e lines each contains a triplet u, v, w, which indicates that an edge between nodes u and v has weight w (w is a positive integer).
1 <= n <= 1,000
0 <= e <= n(n-1)/2
0<= u, v <= n
1 <= m, w <= 10,000
Output
Return the index of the node with the maximum number of reachable nodes and print out all the reachable nodes in increasing order of node index in the next line.