Worst-case Network Latency Analysis

You are given an undirected weighted graph representing a network of employees where each node represents an employee and each edge represents a direct communication channel with an associated latency.

Your task is to compute the worst-case (i.e. maximum) shortest path latency between any two employees as well as count the number of employee pairs that share this maximum latency.

Formally, given a graph with n nodes and a set of edges, let \(d(i,j)\) denote the shortest path distance between nodes \(i\) and \(j\). You need to determine:

\(L = \max_{1 \le i < j \le n} d(i,j)\) and count the number of pairs \((i,j)\) such that \(d(i,j)=L\).

You can assume that the graph is connected, and the edges are bidirectional.

inputFormat

The input is read from stdin and has the following format:

T
n1 m1
u v w
u v w
... (m1 lines of edges for test case 1)
n2 m2
u v w
u v w
... (m2 lines of edges for test case 2)
... (T test cases in total)

</p>

where T denotes the number of test cases. For each test case, the first line contains two integers n and m, representing the number of nodes and the number of edges, respectively. The following m lines each contain three integers u, v, and w, indicating that there is an edge between nodes u and v with a latency of w.

outputFormat

For each test case, output a single line to stdout containing two space separated integers: the maximum latency \(L\) and the number of pairs of nodes achieving that latency.

## sample

2
4 5
1 2 3
2 3 4
3 4 5
1 4 9
1 3 2
3 3
1 2 3
2 3 4
1 3 5

9 1
5 1

</p>