Longest K-Vertex Path on Shortest Path Tree

Given a connected undirected graph with n vertices and m edges. Starting at vertex 1, for each vertex v (2 ≤ v ≤ n), you travel from vertex 1 to v following the path with the minimum total length. If there are multiple shortest paths, the one with the lexicographically smallest sequence of vertices is chosen (the lexicographical order is defined on the sequence of vertex numbers, not on the concatenated string). After reaching v you return along the same path to 1, and then proceed to the next vertex until all vertices have been visited.

The set of edges traversed forms a shortest path tree rooted at vertex 1. On this tree, your task is to determine the following for a given integer K:

• The maximum length among all simple paths that contain exactly K vertices. (A simple path is one that visits each vertex at most once; a path with K vertices contains K-1 edges.)
• The number of distinct paths (an unordered pair of endpoints defines a path, i.e. a path from A to B is considered the same as from B to A) achieving that maximum length.

If K = 1, consider each vertex itself as a path of length 0; therefore, the maximum length is 0 and the count is n.

Note: All formulas below are in LaTeX format. The distance between two vertices on the tree is defined as the sum of the weights of the edges along the unique simple path connecting them. In particular, if the lowest common ancestor of vertices u and v is \(\ell\), and if \(d(x)\) denotes the distance from the root (vertex 1) to vertex x, then the distance between u and v is given by

[ \text{distance}(u,v)=d(u)+d(v)-2,d(\ell). ]

Input Format:

The first line contains three integers \(n\), \(m\), and \(K\). Each of the following \(m\) lines contains three integers \(u\), \(v\), and \(w\), denoting an undirected edge between vertices \(u\) and \(v\) with weight \(w\).

Output Format:

Output two integers separated by a space: the maximum length of a simple path that contains exactly \(K\) vertices, and the number of distinct such paths. For \(K=1\), output 0 n (where n is the number of vertices).

inputFormat

The first line contains three integers: n m K.

Then follow m lines, each with three integers u v w representing an undirected edge between vertices u and v with weight w.

outputFormat

Output two integers separated by a space: the maximum length and the number of distinct simple paths (with exactly K vertices) that have this maximum length.

sample

3 2 2
1 2 5
2 3 6

6 1