Description

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

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

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

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

Input

第一行输入三个正整数n,m，K，表示有n个点m条边，要求的路径需要经过K个点。接下来输入m行，每行三个正整数Ai,Bi,Ci(1<=Ai,Bi<=n,1<=Ci<=10000)，表示Ai和Bi间有一条长度为Ci的边。数据保证输入的是连通的无向图。

 

 

Output

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

 

Sample Input

6 6 4

1 2 1

2 3 1

3 4 1

2 5 1

3 6 1

5 6 1

Sample Output

3 4

设$f[i][0/1]$表示到当前分治重心的路径中点数为$i$的路径最大长度和方案数

然后注意细节就可以$A$掉它了

代码：

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 #define M 100010 8 #define inf 1e9 9 using namespace std; 10 int n,m,num,ans1,ans2,S,rt,k; 11 int head[M],dis[M],d[M],g[M],size[M],maxn[M],f[M][2]; 12 bool vis[M]; 13 struct point{ int to,next,dis;}e[M<<1]; 14 struct edge{ int to,dis;}; 15 struct node{ int id,v;}; 16 vector
           
            vec[M]; 17 priority_queue
            
             Q; 18 bool operator < (node a1,node a2) { 19 return a1.v>a2.v; 20 } 21 void add(int from,int to,int dis) { 22 e[++num].next=head[from]; 23 e[num].to=to; 24 e[num].dis=dis; 25 head[from]=num; 26 } 27 void Dijkstra(int s) { 28 memset(dis,63,sizeof(dis)); 29 dis[s]=0; 30 Q.push((node){s,0}); 31 while(!Q.empty()) { 32 int x=Q.top().id;Q.pop(); 33 if(vis[x]) continue; 34 for(int i=0;i
             
              dis[x]+vec[x][i].dis) { 37 dis[to]=dis[x]+vec[x][i].dis; 38 Q.push((node){to,dis[to]}); 39 } 40 } 41 } 42 } 43 void build(int x) { 44 vis[x]=true; 45 for(int i=0;i
              
               k) return; 68 if(ans1