Description

You are given a connected undirected graph with $n$ vertices and $m$ edges. Starting from vertex 1, for each of the other vertices, walk to it once and then return.

When walking to a vertex, choose a path with the smallest total length. If there are multiple shortest paths, choose the one whose sequence of visited vertices is lexicographically smallest (for example, path A is 1,32,11 and path B is 1,3,2,11; path B is lexicographically smaller. Note that we compare the lexicographical order of the vertex sequence, not the lex order of the concatenated string of node labels). After reaching that vertex, return along the same path, then proceed to the next vertex, until all vertices have been visited.

It can be shown that the edges traversed form a shortest path tree. On this shortest path tree, what is the length of the longest simple path that contains $K$ vertices? How many different paths that contain $K$ vertices achieve this maximum length?

A simple path means a path that visits any vertex at most once. Different paths mean the two endpoints are not the same pair; the path from A to B and the path from B to A are considered the same path.

Input Format

The first line contains three positive integers $n, m, K$, meaning there are $n$ vertices and $m$ edges, and the required path must contain $K$ vertices.

Each of the next $m$ lines contains three positive integers $A_i, B_i, C_i$ ($1 \leq A_i, B_i \leq n, 1 \leq C_i \leq 10000$), indicating there is an edge of length $C_i$ between $A_i$ and $B_i$.

It is guaranteed that the input graph is connected and undirected.

Output Format

Output one line with two integers separated by a space. The first integer is the maximum length of a simple path that contains $K$ vertices, and the second integer is the number of different paths that contain $K$ vertices and achieve this maximum length.

6 6 4
1 2 1
2 3 1
3 4 1
2 5 1
3 6 1
5 6 1

3 4

Hint

Constraints: For all testdata, $n \leq 30000$, $m \leq 60000$, $2 \leq K \leq n$.

It is guaranteed that the shortest path tree contains at least one path that visits $K$ vertices.

Translated by ChatGPT 5