Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

int n,m,l;

#define MAXN 30010

vector< pair<int,int> > g[MAXN];

int dis[MAXN];

bool vis[MAXN];

#define INF 0x3f3f3f3f

vector<int> p[MAXN];

struct edge

{

	int to,nxt,v;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

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

{

	e[++edgenum] = (edge){b,lin[a],c};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b],c};lin[b] = edgenum;

	return;

}

void dfs(int k)

{

	vis[k] = true;

	sort(p[k].begin(),p[k].end());

	for(int i = 0;i < p[k].size();++i)

	{

		if(vis[p[k][i]])continue;

		add(k,p[k][i],dis[p[k][i]] - dis[k]);

		dfs(p[k][i]);

	}

	return;

}

int siz[MAXN],d[MAXN],root,s;

void getroot(int k,int fa)

{

	siz[k] = 1;d[k] = 0;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

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

		getroot(e[i].to,k);

		siz[k] += siz[e[i].to];

		d[k] = max(d[k],siz[e[i].to]);

	}

	d[k] = max(d[k],s - siz[k]);

	if(d[k] < d[root])root = k;

	return;

}

int ans1 = 0,ans2 = 0;

int f[2][MAXN];

int maxdep = 0,dep;

int f2[2][MAXN];

void dfs(int k,int fa,int cnt,int d)

{

	dep = max(dep,cnt);

	if(d > f2[0][cnt]){f2[0][cnt] = d;f2[1][cnt] = 0;}

	if(d == f2[0][cnt])++f2[1][cnt];

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa && !vis[e[i].to])

		{

			dfs(e[i].to,k,cnt + 1,d + e[i].v);

		}

	}

	return;

}

void calc(int k)

{

	maxdep = 0;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

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

		dep = 0;

		dfs(e[i].to,k,1,e[i].v);

		dep = min(dep,l);

		for(int x = 1;x <= dep;++x)

		{

			if(f2[0][x] + f[0][l - x - 1] > ans1){ans1 = f2[0][x] + f[0][l - x - 1];ans2 = 0;}

			if(f2[0][x] + f[0][l - x - 1] == ans1)ans2 += f2[1][x] * f[1][l - x - 1];

		}

		for(int x = 1;x <= dep;++x)

		{

			if(f2[0][x] > f[0][x]){f[0][x] = f2[0][x];f[1][x] = 0;}

			if(f2[0][x] == f[0][x])f[1][x] += f2[1][x];

			f2[0][x] = f2[1][x] = 0;

		}

		maxdep = max(maxdep,dep);

	}

	for(int i = 1;i <= maxdep;++i)f[0][i] = f[1][i] = 0;

	return;

}

void divide(int k)

{

	vis[k] = true;

	calc(k);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

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

		s = siz[e[i].to];root = 0;

		getroot(e[i].to,0);

		divide(root);

	}

	return;

}

int main()

{

	scanf("%d%d%d",&n,&m,&l);

	int a,b,c;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d",&a,&b,&c);

		g[a].push_back(make_pair(b,c));

		g[b].push_back(make_pair(a,c));

	}

	priority_queue< pair<int,int> > q;

	q.push(make_pair(0,1));

	memset(dis,0x3f,sizeof(dis));dis[1] = 0;

	while(!q.empty())

	{

		int k = q.top().second;q.pop();

		if(vis[k])continue;

		vis[k] = true;

		for(vector< pair<int,int> >::iterator i = g[k].begin();i != g[k].end();++i)

		{

			if(dis[i -> first] > dis[k] + i -> second)

			{

				dis[i -> first] = dis[k] + i -> second;

				q.push(make_pair(-dis[i -> first],i -> first));

			}

		}

	}

	for(int k = 1;k <= n;++k)

	{

		for(vector< pair<int,int> >::iterator i = g[k].begin();i != g[k].end();++i)

		{

			if(dis[i -> first] == dis[k] + i -> second)p[k].push_back(i -> first);

		}

	}

	memset(vis,false,sizeof(vis));

	dfs(1);

	root = 0;d[0] = INF;s = n;

	memset(vis,false,sizeof(vis));

	memset(f2,0,sizeof(f2));

	memset(f,0,sizeof(f));

	getroot(1,0);

	f[1][0] = 1;

	divide(root);

	cout << ans1 << " " << ans2 << endl;

	return 0;

}