{"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\"\u003eYou are given n points and m undirected edges, each edge has a length d and a cost p. You are also given a starting point s and an ending point t. Your task is to output the shortest distance and its cost from the starting point to the ending point. If there are multiple routes with the same shortest distance, output the one with the least cost.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"Input n and m, where the points are numbered from 1 to n. Then there are m lines, each containing 4 numbers a, b, d, p, indicating an edge between a and b with a length of d and a cost of p. The last line contains two numbers s and t, representing the starting point s and the ending point t. The input ends when n and m are both 0. \u003cbr\u003e(1\u0026lt;n\u0026lt;\u003d1000, 0\u0026lt;m\u0026lt;100000, s !\u003d t)"}},{"title":"Output","value":{"format":"HTML","content":"Output a line with two numbers: the shortest distance and its cost."}},{"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\u003e3 2\r\n1 2 5 6\r\n2 3 4 5\r\n1 3\r\n0 0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e9 11\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}