给一个包含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行，每行三个正整数Ai,Bi,Ci(1<=Ai,Bi<=n,1<=Ci<=10000)，表示Ai和Bi间有一条长度为Ci的边。数据保证输入的是连通的无向图。

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

对于所有数据n<=30000,m<=60000，2<=K<=n。

数据保证最短路径树上至少存在一条长度为K的路径。

2016.12.7新加数据一组by - wyxxqz-150137

#include <cstdio>

#include <cstring>

#include <iostream>

#include <queue>

#include <utility>

#include <vector>

#include <algorithm>

#define mp(A,B)	make_pair(A,B)

#define fir(_) ((_).first)

#define sec(_) ((_).second)

using namespace std;

typedef pair<int,int> pii;

const int maxn=30010;

const int inf=0x3f3f3f3f;

int n,m,K,cnt,root,tot,maxx,ans,sum,d;

int to[maxn<<1],next[maxn<<1],val[maxn<<1],head[maxn],dis[maxn],vis[maxn],dep[maxn];

int fl[maxn],fs[maxn],gl[maxn],gs[maxn],siz[maxn];

vector<pii> e[maxn];

priority_queue<pii> pq;

void add(int a,int b,int c)

{

	//printf("%d %d %d\n",a,b,c);

	to[cnt]=b,val[cnt]=c,next[cnt]=head[a],head[a]=cnt++;

}

void dijkstra()

{

	memset(dis,0x3f,sizeof(dis));

	dis[1]=0;

	int i,u;

	pii y;

	pq.push(mp(0,-1));

	while(!pq.empty())

	{

		u=-sec(pq.top()),pq.pop();

		if(vis[u])	continue ;

		vis[u]=1;

		for(int i=0;i<e[u].size();i++)

		{

			y=e[u][i];

			if(dis[fir(y)]>dis[u]+sec(y))

				dis[fir(y)]=dis[u]+sec(y),pq.push(mp(-dis[fir(y)],-fir(y)));

		}

	}

	memset(vis,0,sizeof(vis));

}

void Dfs(int x)

{

	vis[x]=1;

	for(int i=0;i<e[x].size();i++)

	{

		pii y=e[x][i];

		if(!vis[fir(y)]&&dis[fir(y)]==dis[x]+sec(y))

			Dfs(fir(y)),add(x,fir(y),sec(y)),add(fir(y),x,sec(y));

	}

}

void getr(int x,int fa)

{

	siz[x]=1;

	int i,mx=0;

	for(i=head[x];i!=-1;i=next[i])

	{

		if(vis[to[i]]||to[i]==fa)	continue;

		getr(to[i],x),siz[x]+=siz[to[i]];

		mx=max(mx,siz[to[i]]);

	}

	if(maxx>max(tot-siz[x],mx))	maxx=max(tot-siz[x],mx),root=x;

}

void getd(int x,int fa,int dep,int len)

{

	if(dep>=K)	return ;

	d=max(d,dep);

	if(gl[dep]<len)	gl[dep]=len,gs[dep]=0;

	if(gl[dep]==len)	gs[dep]++;

	for(int i=head[x];i!=-1;i=next[i])

	{

		if(vis[to[i]]||to[i]==fa)	continue;

		getd(to[i],x,dep+1,len+val[i]);

	}

}

void dfs(int x)

{

	vis[x]=1;

	int i,j,dd=0;

	fs[0]=1;

	for(i=head[x];i!=-1;i=next[i])

	{

		if(vis[to[i]])	continue;

		d=0,getd(to[i],x,1,val[i]),dd=max(dd,d);

		for(j=1;j<=d;j++)

		{

			if(ans<fl[K-j-1]+gl[j])	ans=fl[K-j-1]+gl[j],sum=0;

			if(ans==fl[K-j-1]+gl[j])	sum+=fs[K-j-1]*gs[j];

		}

		for(j=1;j<=d;j++)

		{

			if(fl[j]<gl[j])	fl[j]=gl[j],fs[j]=0;

			if(fl[j]==gl[j])	fs[j]+=gs[j];

			gl[j]=-inf,gs[j]=0;

		}

	}

	for(i=1;i<=dd;i++)	fl[i]=-inf,fs[i]=0;

	for(i=head[x];i!=-1;i=next[i])

	{

		if(vis[to[i]])	continue;

		tot=siz[to[i]],maxx=1<<30,getr(to[i],x),dfs(root);

	}

}

int rd()

{

	int ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();

	return ret*f;

}

int main()

{

	//freopen("bz4016.in","r",stdin);

	//freopen("bz4016.out","w",stdout);

	n=rd(),m=rd(),K=rd();

	int i,a,b,c;

	for(i=1;i<=m;i++)	a=rd(),b=rd(),c=rd(),e[a].push_back(mp(b,c)),e[b].push_back(mp(a,c));

	for(i=1;i<=n;i++)	sort(e[i].begin(),e[i].end());

	memset(head,-1,sizeof(head));

	dijkstra(),Dfs(1);

	memset(vis,0,sizeof(vis));

	for(i=1;i<=n;i++)	fl[i]=gl[i]=-inf;

	tot=n,maxx=1<<30,getr(1,0),dfs(root);

	printf("%d %d",ans,sum);

	return 0;

}