{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cstyle type\u003d\"text/css\"\u003e .sampledata { font-family: \"Courier New\", Courier, monospace; white-space: pre; }\u003c/style\u003e\u003cdiv\u003e\n \u003cspan style\u003d\"font-size: medium\"\u003ea180285非常喜欢滑雪。他来到一座雪山,这里分布着M条供滑行的轨道和N个轨道\u003c/span\u003e\n \u003cspan style\u003d\"font-size: medium\"\u003e之间的交点(同时也是景点),而且每个景点都有一编号i(1\u0026lt;\u003di\u0026lt;\u003dN)和一高度Hi。a180285\u003c/span\u003e\n \u003cspan style\u003d\"font-size: medium\"\u003e能从景点i 滑到景点j 当且仅当存在一条i 和j 之间的边,且i 的高度不小于j。 \u003c/span\u003e\n \u003cspan style\u003d\"font-size: medium\"\u003e与其他滑雪爱好者不同,a180285喜欢用最短的滑行路径去访问尽量多的景点。如果仅\u003c/span\u003e\n \u003cspan style\u003d\"font-size: medium\"\u003e仅访问一条路径上的景点,他会觉得数量太少。于是a180285拿出了他随身携带的时间胶囊。\u003c/span\u003e\n \u003cspan style\u003d\"font-size: medium\"\u003e这是一种很神奇的药物,吃下之后可以立即回到上个经过的景点(不用移动也不被认为是\u003c/span\u003e\n \u003cspan style\u003d\"font-size: medium\"\u003ea180285 滑行的距离)。请注意,这种神奇的药物是可以连续食用的,即能够回到较长时间\u003c/span\u003e\n \u003cspan style\u003d\"font-size: medium\"\u003e之前到过的景点(比如上上个经过的景点和上上上个经过的景点)。 \u003c/span\u003e\n \u003cspan style\u003d\"font-size: medium\"\u003e现在,a180285站在1号景点望着山下的目标,心潮澎湃。他十分想知道在不考虑时间\u003c/span\u003e\n\u003c/div\u003e \n\u003cdiv\u003e\n \u003cspan style\u003d\"font-size: medium\"\u003e胶囊消耗的情况下,以最短滑行距离滑到尽量多的景点的方案(即满足经过景点数最大的前\u003c/span\u003e\n \u003cspan style\u003d\"font-size: medium\"\u003e提下使得滑行总距离最小)。你能帮他求出最短距离和景点数吗? \u003c/span\u003e\n\u003c/div\u003e \n\u003cdiv\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv\u003e\n \u003cspan style\u003d\"font-size: medium\"\u003e输入的第一行是两个整数N,M。 \u003c/span\u003e\n\u003c/div\u003e \n\u003cdiv\u003e\n \u003cspan style\u003d\"font-size: medium\"\u003e接下来1行有N个整数Hi,分别表示每个景点的高度。 \u003c/span\u003e\n\u003c/div\u003e \n\u003cdiv\u003e\n \u003cspan style\u003d\"font-size: medium\"\u003e接下来M行,表示各个景点之间轨道分布的情况。每行3个整数,Ui,Vi,Ki。表示\u003c/span\u003e\n\u003c/div\u003e \n\u003cdiv\u003e\n \u003cspan style\u003d\"font-size: medium\"\u003e编号为Ui的景点和编号为Vi的景点之间有一条长度为Ki的轨道。 \u003c/span\u003e\n\u003c/div\u003e \n\u003cdiv\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv\u003e\n \u0026nbsp;\n\u003c/div\u003e \n\u003cdiv\u003e\n \u003cspan style\u003d\"font-size: medium\"\u003e输出一行,表示a180285最多能到达多少个景点,以及此时最短的滑行距离总和。\u0026nbsp;\u003c/span\u003e\n\u003c/div\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cspan class\u003dsampledata\u003e \r\n3 3 \r\n3 2 1 \r\n1 2 1 \r\n2 3 1 \r\n1 3 10 \r\n\u003c/span\u003e\u003c/div\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cspan class\u003dsampledata\u003e3 2 \r\n\u003c/span\u003e\u003c/div\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cp\u003e\u003c/p\u003e\n\u003cp\u003e【数据范围】 \u003cbr\u003e\u003cbr\u003e \u0026nbsp;\u0026nbsp;\u0026nbsp; 对于30%的数据,保证 1\u0026lt;\u003dN\u0026lt;\u003d2000 \u003cbr\u003e\u003cbr\u003e \u0026nbsp;\u0026nbsp;\u0026nbsp; 对于100%的数据,保证 1\u0026lt;\u003dN\u0026lt;\u003d100000 \u003cbr\u003e\u003cbr\u003e 对于所有的数据,保证 1\u0026lt;\u003dM\u0026lt;\u003d1000000,1\u0026lt;\u003dHi\u0026lt;\u003d1000000000,1\u0026lt;\u003dKi\u0026lt;\u003d1000000000。\u003cbr\u003e\u003cbr\u003e \u003c/p\u003e\n\u003cp\u003e\u003c/p\u003e"}}]}