时间限制：1秒　　内存限制：256M

---

【题目描述】

　　给一个包含 \(n\) 个点，\(m\) 条边的无向连通图。从顶点 1 出发，往其余所有点分别走一次并返回。

　　往某一个点走时，选择总长度最短的路径走。若有多条长度最短的路径，则选择经过的顶点序列字典序最小的那条路径（如路径 \(A\) 为 1,32,11，路径 \(B\) 为 1,3,2,11，路径 \(B\) 字典序较小。注意是序列的字典序的最小，而非路径中节点编号相连的字符串字典序最小）。到达该点后按原路返回，然后往其他点走，直到所有点都走过。

　　可以知道，经过的边会构成一棵最短路径树。请问，在这棵最短路径树上，最长的包含 \(k\) 个点的简单路径长度为多长？长度为该最长长度的不同路径有多少条？

　　这里的简单路径是指：对于一个点最多只经过一次的路径。不同路径是指路径两端端点至少有一个不同，点 \(A\) 到点 \(B\) 的路径和点 \(B\) 到点 \(A\) 视为同一条路径。

【输入格式】

　　第一行输入三个正整数 \(n,m,k\)，表示有 \(n\) 个点 \(m\) 条边，要求的路径需要经过 \(k\) 个点。
　　接下来输入 \(m\) 行，每行三个正整数 \(A_i,B_i,C_i（1\leq A_i,B_i\leq n,1\leq C_i\leq 10000）\)，表示 \(A_i\) 和 \(B_i\) 间有一条长度为 \(C_i\) 的边。数据保证输入的是连通的无向图。

【输出格式】

　　输出一行两个整数，以一个空格隔开，第一个整数表示包含 \(k\) 个点的路径最长为多长，第二个整数表示这样的不同的最长路径有多少条。

【输入输出样例】

　Input

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

　Output

3 4

【数据限制】

　　对于所有数据，\(n\leq 30000,m\leq 60000，2\leq k\leq n\)。数据保证最短路径树上至少存在一条长度为 k 的路径。

【来源】

　　Mr.he