#pragma comment(linker, ”/STACK:38777216“
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <stack>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <time.h>
#include <map>
#include <set>
using namespace std;
const int N = 60005;
const int inf = 1000 * 1000 * 1000;
const int mod = 1000 * 1000 * 1000 + 7;
int n,m,k;
queue <int> q;
bool mark[N];
vector < pair<int , int> > v[N];
vector < pair<int , int> > g[N];
vector < pair< int , pair<int,int> > > pp;
queue <int> pl;
int D[N];
set < pair<int,int> > Q;
set < pair<int,int> >::iterator it;
bool used[N];
int gag , nn , mn;
int order[N];
map <int,int> mp , mp1;
int answ1 , answ2;
void dfs(int v,int p){
order[v] = 1;
nn++;
for(int i=0;i<(int)g[v].size();i++){
int to = g[v][i].first;
if(to == p || used[to])continue;
dfs(to , v);
order[v] += order[to];
}
}
void dfs1(int v,int p){
int T = nn - order[v];
for(int i=0;i<(int)g[v].size();i++){
int to = g[v][i].first;
if(to == p || used[to])continue;
dfs1(to , v);
T = max(T , order[to]);
}
if(mn == -1 || T < mn){
mn = T;
gag = v;
}
}
void made(int v,int p){
order[v] = 1;
for(int i=0;i<(int)g[v].size();i++){
int to = g[v][i].first;
if(to == p || used[to])continue;
made(to , v);
order[v] += order[to];
}
}
int find_centroid(int v){
nn = 0;
dfs(v , -1);
mn = -1;
dfs1(v , -1);
made(gag , -1);
return gag;
}
vector < pair<int,int> > P;
void solve(int v,int p,int r,int sum){
if(r > k)return ;
if(mp1[k - r] != 0){
if(sum + mp[k - r] > answ1){
answ1 = sum + mp[k - r];
answ2 = mp1[k - r];
}
else{
if(sum + mp[k - r] == answ1)
answ2 += mp1[k - r];
}
}
if(p != -1) P.push_back(make_pair(r , sum));
for(int i=0;i<(int)g[v].size();i++){
int to = g[v][i].first;
int len = g[v][i].second;
if(used[to] || to == p)continue;
solve(to , v , r + 1 , sum + len);
if(p == -1){
for(int j=0;j<P.size();j++){
int sz = P[j].first;
int ss = P[j].second;
if(ss > mp[sz]){
mp[sz] = ss;
mp1[sz] = 1;
}
else{
if(ss == mp[sz])
mp1[sz]++;
}
}
P.clear();
}
}
}
void centroid_decomposition(){
queue <int> Q;
Q.push(1);
while(!Q.empty()){
int v = Q.front();
Q.pop();
v = find_centroid(v);
mp.clear();
mp1.clear();
mp1[0] = 1;
solve(v , -1 , 0 , 0);
used[v] = true;
for(int i=0;i<(int)g[v].size();i++){
int to = g[v][i].first;
if(used[to])continue;
if(order[to] == 1)continue;
Q.push(to);
}
}
}
void rec(int vv){
mark[vv] = true;
for(int i=0;i<(int)v[vv].size();i++){
int to = v[vv][i].second;
int len = v[vv][i].first;
if(mark[to])continue;
if(D[vv] + len == D[to]){
g[vv].push_back(make_pair(to , len));
g[to].push_back(make_pair(vv , len));
rec(to);
}
}
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<m;i++){
int aa,bb,cc;
scanf("%d%d%d" , &aa, &bb, &cc);
v[aa].push_back(make_pair(cc,bb));
v[bb].push_back(make_pair(cc,aa));
}
for(int i=1;i<=n;i++) D[i] = -1;
D[1] = 0;
Q.insert(make_pair(0 , 1));
while(!Q.empty()){
it = Q.begin();
int vv = (*it).second;
Q.erase(Q.begin());
for(int i=0;i<(int)v[vv].size();i++){
int to = v[vv][i].second;
int len = v[vv][i].first;
if(D[to] == -1 || D[vv] + len < D[to]){
Q.erase(make_pair(D[to] , to));
D[to] = D[vv] + len;
Q.insert(make_pair(D[to] , to));
}
}
}
for(int i=1;i<=n;i++) sort(v[i].begin(),v[i].end());
rec(1);
k--;
centroid_decomposition();
cout<<answ1<<" "<<answ2<<endl;
return 0;
}
/*
10 9 4
1 2 1
1 3 2
1 4 4
3 5 3
3 6 3
5 7 5
4 8 2
4 9 3
9 10 4
*/
I3ByYWdtYSBjb21tZW50KGxpbmtlciwg4oCdL1NUQUNLOjM4Nzc3MjE24oCcCiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPGNzdHJpbmc+CiNpbmNsdWRlIDxjYXNzZXJ0PgojaW5jbHVkZSA8Y3N0ZGlvPgojaW5jbHVkZSA8c3RhY2s+CiNpbmNsdWRlIDxzdHJpbmc+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxxdWV1ZT4KI2luY2x1ZGUgPGNtYXRoPgojaW5jbHVkZSA8dGltZS5oPgojaW5jbHVkZSA8bWFwPgojaW5jbHVkZSA8c2V0PgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmNvbnN0IGludCBOID0gNjAwMDU7CmNvbnN0IGludCBpbmYgPSAxMDAwICogMTAwMCAqIDEwMDA7CmNvbnN0IGludCBtb2QgPSAxMDAwICogMTAwMCAqIDEwMDAgKyA3OwoKaW50IG4sbSxrOwpxdWV1ZSA8aW50PiBxOwpib29sIG1hcmtbTl07CnZlY3RvciA8IHBhaXI8aW50ICwgaW50PiA+IHZbTl07CnZlY3RvciA8IHBhaXI8aW50ICwgaW50PiA+IGdbTl07CnZlY3RvciA8IHBhaXI8IGludCAsIHBhaXI8aW50LGludD4gPiA+IHBwOwoKcXVldWUgPGludD4gcGw7CgppbnQgRFtOXTsKc2V0IDwgcGFpcjxpbnQsaW50PiA+IFE7CnNldCA8IHBhaXI8aW50LGludD4gPjo6aXRlcmF0b3IgaXQ7Cgpib29sIHVzZWRbTl07CmludCBnYWcgLCBubiAsIG1uOwppbnQgb3JkZXJbTl07CgptYXAgPGludCxpbnQ+IG1wICwgbXAxOwppbnQgYW5zdzEgLCBhbnN3MjsKCnZvaWQgZGZzKGludCB2LGludCBwKXsKICAgIG9yZGVyW3ZdID0gMTsKICAgIG5uKys7CiAgICBmb3IoaW50IGk9MDtpPChpbnQpZ1t2XS5zaXplKCk7aSsrKXsKICAgICAgICBpbnQgdG8gPSBnW3ZdW2ldLmZpcnN0OwogICAgICAgIGlmKHRvID09IHAgfHwgdXNlZFt0b10pY29udGludWU7CiAgICAgICAgZGZzKHRvICwgdik7CiAgICAgICAgb3JkZXJbdl0gKz0gb3JkZXJbdG9dOwogICAgfQp9Cgp2b2lkIGRmczEoaW50IHYsaW50IHApewogICAgaW50IFQgPSBubiAtIG9yZGVyW3ZdOwogICAgZm9yKGludCBpPTA7aTwoaW50KWdbdl0uc2l6ZSgpO2krKyl7CiAgICAgICAgaW50IHRvID0gZ1t2XVtpXS5maXJzdDsKICAgICAgICBpZih0byA9PSBwIHx8IHVzZWRbdG9dKWNvbnRpbnVlOwogICAgICAgIGRmczEodG8gLCB2KTsKICAgICAgICBUID0gbWF4KFQgLCBvcmRlclt0b10pOwogICAgfQogICAgaWYobW4gPT0gLTEgfHwgVCA8IG1uKXsKICAgICAgICBtbiA9IFQ7CiAgICAgICAgZ2FnID0gdjsKICAgIH0KfQoKdm9pZCBtYWRlKGludCB2LGludCBwKXsKICAgIG9yZGVyW3ZdID0gMTsKICAgIGZvcihpbnQgaT0wO2k8KGludClnW3ZdLnNpemUoKTtpKyspewogICAgICAgIGludCB0byA9IGdbdl1baV0uZmlyc3Q7CiAgICAgICAgaWYodG8gPT0gcCB8fCB1c2VkW3RvXSljb250aW51ZTsKICAgICAgICBtYWRlKHRvICwgdik7CiAgICAgICAgb3JkZXJbdl0gKz0gb3JkZXJbdG9dOwogICAgfQp9CgppbnQgZmluZF9jZW50cm9pZChpbnQgdil7CiAgICBubiA9IDA7CiAgICBkZnModiAsIC0xKTsKICAgIG1uID0gLTE7CiAgICBkZnMxKHYgLCAtMSk7CiAgICBtYWRlKGdhZyAsIC0xKTsKICAgIHJldHVybiBnYWc7Cn0KCnZlY3RvciA8IHBhaXI8aW50LGludD4gPiBQOwoKdm9pZCBzb2x2ZShpbnQgdixpbnQgcCxpbnQgcixpbnQgc3VtKXsKICAgIGlmKHIgPiBrKXJldHVybiA7CiAgICBpZihtcDFbayAtIHJdICE9IDApewogICAgICAgIGlmKHN1bSArIG1wW2sgLSByXSA+IGFuc3cxKXsKICAgICAgICAgICAgYW5zdzEgPSBzdW0gKyBtcFtrIC0gcl07CiAgICAgICAgICAgIGFuc3cyID0gbXAxW2sgLSByXTsKICAgICAgICB9CiAgICAgICAgZWxzZXsKICAgICAgICAgICAgaWYoc3VtICsgbXBbayAtIHJdID09IGFuc3cxKQogICAgICAgICAgICAgICAgYW5zdzIgKz0gbXAxW2sgLSByXTsKICAgICAgICB9CiAgICB9CiAgICBpZihwICE9IC0xKSBQLnB1c2hfYmFjayhtYWtlX3BhaXIociAsIHN1bSkpOwogICAgZm9yKGludCBpPTA7aTwoaW50KWdbdl0uc2l6ZSgpO2krKyl7CiAgICAgICAgaW50IHRvID0gZ1t2XVtpXS5maXJzdDsKICAgICAgICBpbnQgbGVuID0gZ1t2XVtpXS5zZWNvbmQ7CiAgICAgICAgaWYodXNlZFt0b10gfHwgdG8gPT0gcCljb250aW51ZTsKICAgICAgICBzb2x2ZSh0byAsIHYgLCByICsgMSAsIHN1bSArIGxlbik7CiAgICAgICAgaWYocCA9PSAtMSl7CiAgICAgICAgICAgIGZvcihpbnQgaj0wO2o8UC5zaXplKCk7aisrKXsKICAgICAgICAgICAgICAgIGludCBzeiA9IFBbal0uZmlyc3Q7CiAgICAgICAgICAgICAgICBpbnQgc3MgPSBQW2pdLnNlY29uZDsKICAgICAgICAgICAgICAgIGlmKHNzID4gbXBbc3pdKXsKICAgICAgICAgICAgICAgICAgICBtcFtzel0gPSBzczsKICAgICAgICAgICAgICAgICAgICBtcDFbc3pdID0gMTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGVsc2V7CiAgICAgICAgICAgICAgICAgICAgaWYoc3MgPT0gbXBbc3pdKQogICAgICAgICAgICAgICAgICAgICAgICBtcDFbc3pdKys7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICAgICAgUC5jbGVhcigpOwogICAgICAgIH0KICAgIH0KfQoKdm9pZCBjZW50cm9pZF9kZWNvbXBvc2l0aW9uKCl7CiAgICBxdWV1ZSA8aW50PiBROwogICAgUS5wdXNoKDEpOwogICAgd2hpbGUoIVEuZW1wdHkoKSl7CiAgICAgICAgaW50IHYgPSBRLmZyb250KCk7CiAgICAgICAgUS5wb3AoKTsKICAgICAgICB2ID0gZmluZF9jZW50cm9pZCh2KTsKICAgICAgICBtcC5jbGVhcigpOwogICAgICAgIG1wMS5jbGVhcigpOwogICAgICAgIG1wMVswXSA9IDE7CiAgICAgICAgc29sdmUodiAsIC0xICwgMCAsIDApOwogICAgICAgIHVzZWRbdl0gPSB0cnVlOwogICAgICAgIGZvcihpbnQgaT0wO2k8KGludClnW3ZdLnNpemUoKTtpKyspewogICAgICAgICAgICBpbnQgdG8gPSBnW3ZdW2ldLmZpcnN0OwogICAgICAgICAgICBpZih1c2VkW3RvXSljb250aW51ZTsKICAgICAgICAgICAgaWYob3JkZXJbdG9dID09IDEpY29udGludWU7CiAgICAgICAgICAgIFEucHVzaCh0byk7CiAgICAgICAgfQogICAgfQp9Cgp2b2lkIHJlYyhpbnQgdnYpewogICAgbWFya1t2dl0gPSB0cnVlOwogICAgZm9yKGludCBpPTA7aTwoaW50KXZbdnZdLnNpemUoKTtpKyspewogICAgICAgIGludCB0byA9IHZbdnZdW2ldLnNlY29uZDsKICAgICAgICBpbnQgbGVuID0gdlt2dl1baV0uZmlyc3Q7CiAgICAgICAgaWYobWFya1t0b10pY29udGludWU7CiAgICAgICAgaWYoRFt2dl0gKyBsZW4gPT0gRFt0b10pewogICAgICAgICAgICBnW3Z2XS5wdXNoX2JhY2sobWFrZV9wYWlyKHRvICwgbGVuKSk7CiAgICAgICAgICAgIGdbdG9dLnB1c2hfYmFjayhtYWtlX3BhaXIodnYgLCBsZW4pKTsKICAgICAgICAgICAgcmVjKHRvKTsKICAgICAgICB9CiAgICB9Cn0KCmludCBtYWluKCl7CiAgICBzY2FuZigiJWQlZCVkIiwmbiwmbSwmayk7CiAgICBmb3IoaW50IGk9MDtpPG07aSsrKXsKICAgICAgICBpbnQgYWEsYmIsY2M7CiAgICAgICAgc2NhbmYoIiVkJWQlZCIgLCAmYWEsICZiYiwgJmNjKTsKICAgICAgICB2W2FhXS5wdXNoX2JhY2sobWFrZV9wYWlyKGNjLGJiKSk7CiAgICAgICAgdltiYl0ucHVzaF9iYWNrKG1ha2VfcGFpcihjYyxhYSkpOwogICAgfQogICAgZm9yKGludCBpPTE7aTw9bjtpKyspIERbaV0gPSAtMTsKICAgIERbMV0gPSAwOwogICAgUS5pbnNlcnQobWFrZV9wYWlyKDAgLCAxKSk7CiAgICB3aGlsZSghUS5lbXB0eSgpKXsKICAgICAgICBpdCA9IFEuYmVnaW4oKTsKICAgICAgICBpbnQgdnYgPSAoKml0KS5zZWNvbmQ7CiAgICAgICAgUS5lcmFzZShRLmJlZ2luKCkpOwogICAgICAgIGZvcihpbnQgaT0wO2k8KGludCl2W3Z2XS5zaXplKCk7aSsrKXsKICAgICAgICAgICAgaW50IHRvID0gdlt2dl1baV0uc2Vjb25kOwogICAgICAgICAgICBpbnQgbGVuID0gdlt2dl1baV0uZmlyc3Q7CiAgICAgICAgICAgIGlmKERbdG9dID09IC0xIHx8IERbdnZdICsgbGVuIDwgRFt0b10pewogICAgICAgICAgICAgICAgUS5lcmFzZShtYWtlX3BhaXIoRFt0b10gLCB0bykpOwogICAgICAgICAgICAgICAgRFt0b10gPSBEW3Z2XSArIGxlbjsKICAgICAgICAgICAgICAgIFEuaW5zZXJ0KG1ha2VfcGFpcihEW3RvXSAsIHRvKSk7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAgICBmb3IoaW50IGk9MTtpPD1uO2krKykgc29ydCh2W2ldLmJlZ2luKCksdltpXS5lbmQoKSk7CiAgICByZWMoMSk7CiAgICBrLS07CiAgICBjZW50cm9pZF9kZWNvbXBvc2l0aW9uKCk7CiAgICBjb3V0PDxhbnN3MTw8IiAiPDxhbnN3Mjw8ZW5kbDsKICAgIHJldHVybiAwOwp9Ci8qCjEwIDkgNAoxIDIgMQoxIDMgMgoxIDQgNAozIDUgMwozIDYgMwo1IDcgNQo0IDggMgo0IDkgMwo5IDEwIDQKKi8K