{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\n马加尔帝国的皇帝爱德华想要修建一些双向高速公路,以便他可以尽快从首都到达其他城市。因此,他提出了高速公路项目。\n\u003c/p\u003e\n\n\u003cp\u003e\n马加尔帝国有\u003cvar\u003eN\u003c/var\u003e个城市(包括首都),编号从0到\u003cvar\u003eN\u003c/var\u003e - 1(首都是0),并且可以建造\u003cvar\u003eM\u003c/var\u003e条高速公路。修建第\u003cvar\u003ei\u003c/var\u003e条高速公路的成本是\u003cvar\u003eC\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e美元。在第\u003cvar\u003ei\u003c/var\u003e条高速公路上,从城市\u003cvar\u003eX\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e到\u003cvar\u003eY\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e需要花费\u003cvar\u003eD\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e分钟。\n\u003c/p\u003e\n\n\u003cp\u003e\n爱德华希望找到一个最小化从首都到其他城市所需总时间的建设计划,即最小化从首都到城市\u003cvar\u003ei\u003c/var\u003e(1 ≤ \u003cvar\u003ei\u003c/var\u003e ≤ \u003cvar\u003eN\u003c/var\u003e)所需的最短时间之和。在所有可行的计划中,爱德华希望选择成本最小的计划。请帮助他完成这个任务。\n\u003c/p\u003e\n\n\u003ch4\u003e输入\u003c/h4\u003e\n\n\u003cp\u003e有多个测试用例。输入的第一行包含一个整数\u003cvar\u003eT\u003c/var\u003e,表示测试用例的数量。对于每个测试用例:\u003c/p\u003e\n\n\u003cp\u003e\n第一行包含两个整数\u003cvar\u003eN\u003c/var\u003e,\u003cvar\u003eM\u003c/var\u003e(1 ≤ \u003cvar\u003eN\u003c/var\u003e,\u003cvar\u003eM\u003c/var\u003e ≤ 10\u003csup\u003e5\u003c/sup\u003e)。\n\u003c/p\u003e\n\u003cp\u003e\n然后是\u003cvar\u003eM\u003c/var\u003e行,每行包含四个整数\u003cvar\u003eX\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e,\u003cvar\u003eY\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e,\u003cvar\u003eD\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e,\u003cvar\u003eC\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e(0 ≤ \u003cvar\u003eX\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e,\u003cvar\u003eY\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e \u0026lt; \u003cvar\u003eN\u003c/var\u003e,0 \u0026lt; \u003cvar\u003eD\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e,\u003cvar\u003eC\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e \u0026lt; 10\u003csup\u003e5\u003c/sup\u003e)。\n\u003c/p\u003e\n\n\u003ch4\u003e输出\u003c/h4\u003e\n\n\u003cp\u003e\n对于每个测试用例,输出两个整数,表示最小总时间和最小成本,当总时间最小化时。\n\u003c/p\u003e\n\n\u003ch4\u003e样例\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\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\u003e\r\n2\r\n4 5\r\n0 3 1 1\r\n0 1 1 1\r\n0 2 10 10\r\n2 1 1 1\r\n2 3 1 2\r\n4 5\r\n0 3 1 1\r\n0 1 1 1\r\n0 2 10 10\r\n2 1 2 1\r\n2 3 1 2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\r\n4 3\r\n4 4\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}