{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e Given a connected, undirected graph G, a shortest-path tree rooted at vertex v is a spanning tree T of G, such that the path distance from root v to any other vertex u in T is the shortest path distance from v to u in G. \u003cbr\u003e We may construct a shortest-path tree using the following method:\u003cbr\u003e We consider a shortest-path tree rooted at node 1. For every node i in the graph G, we choose a shortest path from root to i. If there are many shortest paths from root to i, we choose the one that the sequence of passing nodes\u0027 number is lexicographically minimum. All edges on the paths that we chose form a shortest-path tree.\u003cbr\u003e Now we want to know how long are the longest simple paths which contain K nodes in the shortest-path tree and how many these paths? Two simple paths are different if the sets of nodes they go through are different.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":" The first line has a number T (T \u0026lt;\u003d 10), indicating the number of test cases.\u003cbr\u003e For each test case, the first line contains three integers n, m, k(1\u0026lt;\u003dn\u0026lt;\u003d30000,1\u0026lt;\u003dm\u0026lt;\u003d60000,2\u0026lt;\u003dk\u0026lt;\u003dn), denote the number of nodes, the number of edges and the nodes of required paths.\u003cbr\u003e Then next m lines, each lines contains three integers a, b, c(1\u0026lt;\u003da, b\u0026lt;\u003dn, 1\u0026lt;\u003dc\u0026lt;\u003d10000),denote there is an edge between a, b and length is c."}},{"title":"Output","value":{"format":"HTML","content":" For each case, output two numbers, denote the length of required paths and the numbers of required paths."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n6 6 4\r\n1 2 1\r\n2 3 1\r\n3 4 1\r\n2 5 1\r\n3 6 1\r\n5 6 1\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3 4\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}