Shortest Path with Minimum Edges

In this problem, you are given an undirected graph with (N) nodes and (M) edges. Each edge has a positive weight (ranging from 1 to (W)). Your task is to find the shortest path from a starting node (S) to a destination node (D) using two criteria:

1. Minimize the number of edges used in the path.
2. If there exist multiple paths with the same number of edges, choose the path with the smallest total weight.

If the starting node (S) and the destination (D) are the same, the answer is (0) edges and a total weight of (0). If there is no valid path between (S) and (D), output (-1).

The input is given via standard input (stdin) and the result should be printed to standard output (stdout). The answer must be provided as two numbers: the minimum number of edges followed by the total weight, separated by a space. If no path exists, output only (-1).

inputFormat

The input format is as follows:

• The first line contains three integers (N), (M), and (W), where (N) is the number of nodes, (M) is the number of edges, and (W) is the maximum possible weight of an edge (this may be used for validation purposes).
• The following (M) lines each contain three integers (u), (v), and (w), representing an undirected edge between nodes (u) and (v) with weight (w).
• The last line contains two integers (S) and (D), representing the starting node and the destination node respectively.

outputFormat

Output a single line. If a valid path exists from (S) to (D), print two integers: the minimum number of edges in the path and the total weight of this path, separated by a space. If no such path exists, print (-1).## sample

6 7 10
1 2 3
1 3 2
2 4 2
3 4 4
4 5 6
5 6 2
3 5 3
1 6

3 7