Problem Description
The graph diameter is the length of the "longest shortest path" between any two vertices of a graph. In other words, a graph's diameter is the longest path which must be traversed in order to travel from any vertex to another when paths which backtrack, detour, or loop are excluded from consideration.
Given an undirected graph, your mission is to count the number of diameters of it.
Input
The input contains multiple test cases.
For each test case, it contains n+1 lines.
Line 1: two integers m, n (2<= m <= 100, 1 <= n <= 4000) indicating that there are m vertices and n edges in the city.
Line 2~n+1: each contains three integers i, j, d (1 <= i, j <= m, 1 <= d <= 100), indicating that there is an edge of length d connecting vertex i and vertex j.
Output
Output the value of the diameter and the number of diameters in a single line, separated by a single space.
Sample Input
4 5
1 2 1
2 3 1
3 4 1
1 4 1
1 3 2
Sample Output
2 5