{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e \u003cspan\u003e\u003ca href\u003d\"http://7xjob4.com1.z0.glb.clouddn.com/a895323a9119b3001d5a90e55c3c53cf\"\u003e \u003cimg alt\u003d\"Download as PDF\" height\u003d\"26\" src\u003d\"https://icpcarchive.ecs.baylor.edu/components/com_onlinejudge/images/button_pdf.png\" title\u003d\"Download as PDF\" width\u003d\"100\"\u003e \u003c/a\u003e\u003c/span\u003e\u003c/p\u003e \n\u003cdiv\u003e \n \u003cp\u003e The army of United Nations launched a new wave of air strikes on \u003cspan\u003eterroristforces\u003c/span\u003e. The objective of the mission is to reduce enemy\u0027s logistical mobility. Each \u003cspan\u003eairstrike\u003c/span\u003e will destroy a path and therefore increase the shipping cost of the shortest \u003cspan\u003epathbetween\u003c/span\u003e two enemy locations. The maximal damage is always desirable.\u003c/p\u003e \n \u003cp\u003e Let\u0027s assume that there are \u003cspan\u003e\u003cem\u003en\u003c/em\u003e\u003c/span\u003e enemy locations connected by \u003cspan\u003e\u003cem\u003em\u003c/em\u003e\u003c/span\u003e bidirectional paths,each with specific shipping cost. Enemy\u0027s total shipping cost is given as \u003cspan\u003e\u003cem\u003ec\u003c/em\u003e \u003d \u003cimg align\u003d\"MIDDLE\" alt\u003d\"$ \\sum^{{n}}_{{i\u003d1}}$\" height\u003d\"34\" src\u003d\"http://uva.onlinejudge.org/external/14/4080img1.png\" width\u003d\"44\"\u003e\u003cimg align\u003d\"MIDDLE\" alt\u003d\"$ \\sum^{{n}}_{{j\u003d1}}$\" height\u003d\"34\" src\u003d\"http://uva.onlinejudge.org/external/14/4080img2.png\" width\u003d\"46\"\u003e\u003cem\u003epath\u003c/em\u003e(\u003cem\u003ei\u003c/em\u003e, \u003cem\u003ej\u003c/em\u003e)\u003c/span\u003e. Here \u003cspan\u003e\u003cem\u003epath\u003c/em\u003e(\u003cem\u003ei\u003c/em\u003e, \u003cem\u003ej\u003c/em\u003e)\u003c/span\u003e is the shortest path between locations \u003cspan\u003e\u003cem\u003ei\u003c/em\u003e\u003c/span\u003e and \u003cspan\u003e\u003cem\u003ej\u003c/em\u003e\u003c/span\u003e. In case \u003cspan\u003e\u003cem\u003ei\u003c/em\u003e\u003c/span\u003e and \u003cspan\u003e\u003cem\u003ej\u003c/em\u003e\u003c/span\u003e are not connected, \u003cspan\u003e\u003cem\u003epath\u003c/em\u003e(\u003cem\u003ei\u003c/em\u003e, \u003cem\u003ej\u003c/em\u003e) \u003d \u003cem\u003eL\u003c/em\u003e\u003c/span\u003e. Each air strike can only destroy one path. The total shipping cost after the strike is noted as \u003cspan\u003e\u003cem\u003ec\u0027\u003c/em\u003e\u003c/span\u003e. In order to \u003cspan\u003emaximizedthe\u003c/span\u003e damage to the enemy, UN\u0027s air force try to find the maximal \u003cspan\u003e\u003cem\u003ec\u0027\u003c/em\u003e - \u003cem\u003ec\u003c/em\u003e\u003c/span\u003e.\u003c/p\u003e \n\u003c/div\u003e \n\u003cp\u003e \u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e The first line \u003cspan\u003eofeach\u003c/span\u003e input case consists \u003cspan\u003eofthree\u003c/span\u003e integers: \u003cspan\u003e \u003cem\u003en\u003c/em\u003e\u003c/span\u003e, \u003cspan\u003e\u003cem\u003em\u003c/em\u003e\u003c/span\u003e, and \u003cspan\u003e\u003cem\u003eL\u003c/em\u003e\u003c/span\u003e. \u003cspan\u003e1 \u0026lt; \u003cspan\u003e\u003cem\u003en\u003c/em\u003e\u003cimg align\u003d\"MIDDLE\" alt\u003d\"$ \\le$\" height\u003d\"31\" src\u003d\"http://uva.onlinejudge.org/external/14/4080img3.png\" width\u003d\"18\"\u003e100\u003c/span\u003e\u003c/span\u003e,\u003cspan\u003e\u003cspan\u003e1\u003cimg align\u003d\"MIDDLE\" alt\u003d\"$ \\le$\" height\u003d\"31\" src\u003d\"http://uva.onlinejudge.org/external/14/4080img3.png\" width\u003d\"18\"\u003e\u003cem\u003em\u003c/em\u003e\u003cimg align\u003d\"MIDDLE\" alt\u003d\"$ \\le$\" height\u003d\"31\" src\u003d\"http://uva.onlinejudge.org/external/14/4080img3.png\" width\u003d\"18\"\u003e1000\u003c/span\u003e\u003c/span\u003e, \u003cspan\u003e\u003cspan\u003e1\u003cimg align\u003d\"MIDDLE\" alt\u003d\"$ \\le$\" height\u003d\"31\" src\u003d\"http://uva.onlinejudge.org/external/14/4080img3.png\" width\u003d\"18\"\u003e\u003cem\u003eL\u003c/em\u003e\u003cimg align\u003d\"MIDDLE\" alt\u003d\"$ \\le$\" height\u003d\"31\" src\u003d\"http://uva.onlinejudge.org/external/14/4080img3.png\" width\u003d\"18\"\u003e10\u003csup\u003e\u003cimg align\u003d\"BOTTOM\" alt\u003d\"$\\scriptstyle \\wedge$\" height\u003d\"14\" src\u003d\"http://uva.onlinejudge.org/external/14/4080img4.png\" width\u003d\"14\"\u003e\u003c/sup\u003e8\u003c/span\u003e\u003c/span\u003e. Each \u003cspan\u003eofthe\u003c/span\u003e following \u003cspan\u003e\u003cem\u003em\u003c/em\u003e\u003c/span\u003e lines contains three integers: \u003cspan\u003e\u003cem\u003ea\u003c/em\u003e\u003c/span\u003e,\u003cspan\u003e\u003cem\u003eb\u003c/em\u003e\u003c/span\u003e, \u003cspan\u003e \u003cem\u003es\u003c/em\u003e\u003c/span\u003e, indicating length of the path between \u003cspan\u003e\u003cem\u003ea\u003c/em\u003e\u003c/span\u003e and \u003cspan\u003e\u003cem\u003eb\u003c/em\u003e\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e For each case, output the total shipping cost before the air strike and the \u003cspan\u003emaximaltotal\u003c/span\u003e shipping cost after the strike. Output them in one line separated by a space.\u003c/p\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e\r\n4 6 1000\r\n1 3 2\r\n1 4 4\r\n2 1 3\r\n2 3 3\r\n3 4 1\r\n4 2 2\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e\r\n28 38\u003c/pre\u003e"}}]}