{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cstyle\u003e\n\u003c!--\n /* Font Definitions */\n @font-face\n\t{font-family:Mangal;\n\tpanose-1:2 4 5 3 5 2 3 3 2 2;}\n@font-face\n\t{font-family:\"Cambria Math\";\n\tpanose-1:2 4 5 3 5 4 6 3 2 4;}\n@font-face\n\t{font-family:Cambria;\n\tpanose-1:2 4 5 3 5 4 6 3 2 4;}\n@font-face\n\t{font-family:Calibri;\n\tpanose-1:2 15 5 2 2 2 4 3 2 4;}\n@font-face\n\t{font-family:Tahoma;\n\tpanose-1:2 11 6 4 3 5 4 4 2 4;}\n@font-face\n\t{font-family:Garamond;\n\tpanose-1:2 2 4 4 3 3 1 1 8 3;}\n@font-face\n\t{font-family:Verdana;\n\tpanose-1:2 11 6 4 3 5 4 4 2 4;}\n@font-face\n\t{font-family:\"Bernard MT Condensed\";\n\tpanose-1:2 5 8 6 6 9 5 2 4 4;}\n@font-face\n\t{font-family:\"Bookman Old Style\";\n\tpanose-1:2 5 6 4 5 5 5 2 2 4;}\n@font-face\n\t{font-family:\"Courier 10 Pitch\";}\n@font-face\n\t{font-family:\"DejaVu Sans\";}\n@font-face\n\t{font-family:\"\\@Courier 10 Pitch\";}\n@font-face\n\t{font-family:\"\\@DejaVu Sans\";}\n /* Style Definitions */\n p.MsoNormal, li.MsoNormal, div.MsoNormal\n\t{margin-top:0in;\n\tmargin-right:0in;\n\tmargin-bottom:10.0pt;\n\tmargin-left:0in;\n\ttext-align:justify;\n\tline-height:115%;\n\tfont-size:12.0pt;\n\tfont-family:\"Garamond\",\"serif\";}\nh1\n\t{mso-style-link:\"Heading 1 Char\";\n\tmargin:0in;\n\tmargin-bottom:.0001pt;\n\ttext-align:justify;\n\tline-height:115%;\n\tpage-break-after:avoid;\n\tfont-size:14.0pt;\n\tfont-family:\"Cambria\",\"serif\";\n\tcolor:green;}\nh2\n\t{mso-style-link:\"Heading 2 Char\";\n\tmargin:0in;\n\tmargin-bottom:.0001pt;\n\ttext-align:justify;\n\tpage-break-after:avoid;\n\tfont-size:16.0pt;\n\tfont-family:\"Arial\",\"sans-serif\";\n\tcolor:black;}\nh3\n\t{mso-style-link:\"Heading 3 Char\";\n\tmargin-top:10.0pt;\n\tmargin-right:0in;\n\tmargin-bottom:0in;\n\tmargin-left:0in;\n\tmargin-bottom:.0001pt;\n\ttext-align:justify;\n\tline-height:115%;\n\tpage-break-after:avoid;\n\tfont-size:12.0pt;\n\tfont-family:\"Garamond\",\"serif\";\n\tcolor:#4F81BD;}\np.MsoHeader, li.MsoHeader, div.MsoHeader\n\t{mso-style-link:\"Header Char\";\n\tmargin:0in;\n\tmargin-bottom:.0001pt;\n\ttext-align:justify;\n\tfont-size:12.0pt;\n\tfont-family:\"Garamond\",\"serif\";}\np.MsoFooter, li.MsoFooter, div.MsoFooter\n\t{mso-style-link:\"Footer Char\";\n\tmargin:0in;\n\tmargin-bottom:.0001pt;\n\ttext-align:justify;\n\tfont-size:12.0pt;\n\tfont-family:\"Garamond\",\"serif\";}\np.MsoTitle, li.MsoTitle, div.MsoTitle\n\t{mso-style-link:\"Title Char\";\n\tmargin-top:0in;\n\tmargin-right:0in;\n\tmargin-bottom:12.0pt;\n\tmargin-left:0in;\n\ttext-align:center;\n\tfont-size:36.0pt;\n\tfont-family:\"Bernard MT Condensed\",\"serif\";\n\tcolor:green;\n\tletter-spacing:.25pt;}\np.MsoTitleCxSpFirst, li.MsoTitleCxSpFirst, div.MsoTitleCxSpFirst\n\t{mso-style-link:\"Title Char\";\n\tmargin:0in;\n\tmargin-bottom:.0001pt;\n\ttext-align:center;\n\tfont-size:36.0pt;\n\tfont-family:\"Bernard MT Condensed\",\"serif\";\n\tcolor:green;\n\tletter-spacing:.25pt;}\np.MsoTitleCxSpMiddle, li.MsoTitleCxSpMiddle, div.MsoTitleCxSpMiddle\n\t{mso-style-link:\"Title Char\";\n\tmargin:0in;\n\tmargin-bottom:.0001pt;\n\ttext-align:center;\n\tfont-size:36.0pt;\n\tfont-family:\"Bernard MT Condensed\",\"serif\";\n\tcolor:green;\n\tletter-spacing:.25pt;}\np.MsoTitleCxSpLast, li.MsoTitleCxSpLast, div.MsoTitleCxSpLast\n\t{mso-style-link:\"Title Char\";\n\tmargin-top:0in;\n\tmargin-right:0in;\n\tmargin-bottom:12.0pt;\n\tmargin-left:0in;\n\ttext-align:center;\n\tfont-size:36.0pt;\n\tfont-family:\"Bernard MT Condensed\",\"serif\";\n\tcolor:green;\n\tletter-spacing:.25pt;}\np.MsoSubtitle, li.MsoSubtitle, div.MsoSubtitle\n\t{mso-style-link:\"Subtitle Char\";\n\tmargin-top:6.0pt;\n\tmargin-right:0in;\n\tmargin-bottom:0in;\n\tmargin-left:0in;\n\tmargin-bottom:.0001pt;\n\ttext-align:center;\n\tline-height:115%;\n\tfont-size:24.0pt;\n\tfont-family:\"Bookman Old Style\",\"serif\";\n\tletter-spacing:.75pt;\n\tfont-weight:bold;}\np.MsoBodyText3, li.MsoBodyText3, div.MsoBodyText3\n\t{mso-style-link:\"Body Text 3 Char\";\n\tmargin:0in;\n\tmargin-bottom:.0001pt;\n\ttext-align:justify;\n\tfont-size:12.0pt;\n\tfont-family:\"Verdana\",\"sans-serif\";\n\tcolor:black;}\na:link, span.MsoHyperlink\n\t{color:blue;\n\ttext-decoration:underline;}\na:visited, span.MsoHyperlinkFollowed\n\t{color:purple;\n\ttext-decoration:underline;}\npre\n\t{mso-style-link:\"HTML Preformatted Char\";\n\tmargin:0in;\n\tmargin-bottom:.0001pt;\n\ttext-align:justify;\n\tfont-size:10.0pt;\n\tfont-family:\"Courier New\";}\np.MsoAcetate, li.MsoAcetate, div.MsoAcetate\n\t{mso-style-link:\"Balloon Text Char\";\n\tmargin:0in;\n\tmargin-bottom:.0001pt;\n\ttext-align:justify;\n\tfont-size:8.0pt;\n\tfont-family:\"Tahoma\",\"sans-serif\";}\np.MsoNoSpacing, li.MsoNoSpacing, div.MsoNoSpacing\n\t{margin:0in;\n\tmargin-bottom:.0001pt;\n\tfont-size:12.0pt;\n\tfont-family:\"Garamond\",\"serif\";}\np.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph\n\t{margin-top:0in;\n\tmargin-right:0in;\n\tmargin-bottom:10.0pt;\n\tmargin-left:.5in;\n\tline-height:115%;\n\tfont-size:11.0pt;\n\tfont-family:\"Calibri\",\"sans-serif\";}\np.MsoListParagraphCxSpFirst, li.MsoListParagraphCxSpFirst, div.MsoListParagraphCxSpFirst\n\t{margin-top:0in;\n\tmargin-right:0in;\n\tmargin-bottom:0in;\n\tmargin-left:.5in;\n\tmargin-bottom:.0001pt;\n\tline-height:115%;\n\tfont-size:11.0pt;\n\tfont-family:\"Calibri\",\"sans-serif\";}\np.MsoListParagraphCxSpMiddle, li.MsoListParagraphCxSpMiddle, div.MsoListParagraphCxSpMiddle\n\t{margin-top:0in;\n\tmargin-right:0in;\n\tmargin-bottom:0in;\n\tmargin-left:.5in;\n\tmargin-bottom:.0001pt;\n\tline-height:115%;\n\tfont-size:11.0pt;\n\tfont-family:\"Calibri\",\"sans-serif\";}\np.MsoListParagraphCxSpLast, li.MsoListParagraphCxSpLast, div.MsoListParagraphCxSpLast\n\t{margin-top:0in;\n\tmargin-right:0in;\n\tmargin-bottom:10.0pt;\n\tmargin-left:.5in;\n\tline-height:115%;\n\tfont-size:11.0pt;\n\tfont-family:\"Calibri\",\"sans-serif\";}\nspan.MsoSubtleEmphasis\n\t{color:gray;\n\tfont-style:italic;}\nspan.HeaderChar\n\t{mso-style-name:\"Header Char\";\n\tmso-style-link:Header;}\nspan.FooterChar\n\t{mso-style-name:\"Footer Char\";\n\tmso-style-link:Footer;}\nspan.Heading2Char\n\t{mso-style-name:\"Heading 2 Char\";\n\tmso-style-link:\"Heading 2\";\n\tfont-family:\"Arial\",\"sans-serif\";\n\tcolor:black;\n\tfont-weight:bold;}\nspan.BodyText3Char\n\t{mso-style-name:\"Body Text 3 Char\";\n\tmso-style-link:\"Body Text 3\";\n\tfont-family:\"Verdana\",\"sans-serif\";\n\tcolor:black;}\nspan.BalloonTextChar\n\t{mso-style-name:\"Balloon Text Char\";\n\tmso-style-link:\"Balloon Text\";\n\tfont-family:\"Tahoma\",\"sans-serif\";}\nspan.HTMLPreformattedChar\n\t{mso-style-name:\"HTML Preformatted Char\";\n\tmso-style-link:\"HTML Preformatted\";\n\tfont-family:\"Courier New\";}\nspan.TitleChar\n\t{mso-style-name:\"Title Char\";\n\tmso-style-link:Title;\n\tfont-family:\"Bernard MT Condensed\",\"serif\";\n\tcolor:green;\n\tletter-spacing:.25pt;}\nspan.Heading3Char\n\t{mso-style-name:\"Heading 3 Char\";\n\tmso-style-link:\"Heading 3\";\n\tfont-family:\"Cambria\",\"serif\";\n\tcolor:#4F81BD;\n\tfont-weight:bold;}\nspan.Heading1Char\n\t{mso-style-name:\"Heading 1 Char\";\n\tmso-style-link:\"Heading 1\";\n\tfont-family:\"Cambria\",\"serif\";\n\tcolor:green;\n\tfont-weight:bold;}\nspan.SubtitleChar\n\t{mso-style-name:\"Subtitle Char\";\n\tmso-style-link:Subtitle;\n\tfont-family:\"Bookman Old Style\",\"serif\";\n\tletter-spacing:.75pt;\n\tfont-weight:bold;}\np.SampleIO, li.SampleIO, div.SampleIO\n\t{mso-style-name:SampleIO;\n\tmargin-top:0in;\n\tmargin-right:0in;\n\tmargin-bottom:0in;\n\tmargin-left:16.4pt;\n\tmargin-bottom:.0001pt;\n\tfont-size:12.0pt;\n\tfont-family:\"Courier 10 Pitch\";}\nspan.apple-style-span\n\t{mso-style-name:apple-style-span;}\np.msonospacing0, li.msonospacing0, div.msonospacing0\n\t{mso-style-name:msonospacing;\n\tmargin-right:0in;\n\tmargin-left:0in;\n\tfont-size:12.0pt;\n\tfont-family:\"Times New Roman\",\"serif\";}\n.MsoChpDefault\n\t{font-size:10.0pt;}\n /* Page Definitions */\n @page Section1\n\t{size:8.5in 11.0in;\n\tmargin:1.0in 1.0in 1.0in 1.0in;}\ndiv.Section1\n\t{page:Section1;}\n /* List Definitions */\n ol\n\t{margin-bottom:0in;}\nul\n\t{margin-bottom:0in;}\n--\u003e\n\u003c/style\u003e \n \u003cp class\u003d\"MsoNormal\"\u003eСкоро у наших друзей свадьба! Теперь мы хотим купить свадебный подарок. Так как свадьба действительно уже совсем скоро, мы решили купить подарок по пути на свадьбу. Мы хотим посетить как можно больше магазинов по пути. Город можно представить как \u003cb\u003eN\u003c/b\u003e вершин и \u003cb\u003eM\u003c/b\u003e ребер. \u003cb\u003eN\u003c/b\u003e вершин обозначают \u003cb\u003eN\u003c/b\u003e перекрестков и \u003cb\u003eM\u003c/b\u003e ребер обозначают \u003cb\u003eM\u003c/b\u003e двунаправленных дорог соединяющих перекрестки. Для каждой дороги изветсно, сколько времени требуется, чтобы по ней проехать. Свадьба будет проходить на перекрестке \u003cb\u003eN-1\u003c/b\u003e, а мы сейчас находимся в перекрестке \u003cb\u003e0\u003c/b\u003e. В городе ровно \u003cb\u003eS\u003c/b\u003e магазинов, расположенных в различных перекрестках.\u003c/p\u003e \n \u003cp class\u003d\"MsoNormal\"\u003eЗная расположение всех перекрестков, найдите путь из \u003cb\u003e0\u003c/b\u003e в \u003cb\u003eN-1\u003c/b\u003e, который посещает как можно больше магазинов за минимальное время (в первую очередь максимизируйте количество магазинов, и только потом время). Мы можем посетить перекресток больше одного раза.\u003c/p\u003e \n "}},{"title":"Input","value":{"format":"HTML","content":" \n \u003cp class\u003d\"MsoNormal\"\u003eПервая строка входного файла содержит число \u003cb\u003eT (\u003c/b\u003e\u003cb\u003e≤ 50)\u003c/b\u003e - количество тестов.\u003c/p\u003e \n \u003cp class\u003d\"MsoNormal\"\u003e\u003cspan style\u003d\"line-height:115%;color:black\"\u003eКаждый тест начинается с трех чисел\u0026nbsp;\u003cb\u003eN (2 ≤ N ≤ 500)\u003c/b\u003e, \u003cb\u003eM (1 ≤ M ≤ 10000)\u003c/b\u003e \u003cb\u003eS (0 ≤ S ≤ 15)\u003c/b\u003e. Следующая строка содержит \u003cb\u003eS\u003c/b\u003e чисел обозначающие расположения магазинов. Каждая из следующих \u003cb\u003eM\u003c/b\u003e строк содержат три числа \u003cb\u003eu\u003c/b\u003e, \u003cb\u003ev, w\u003c/b\u003e \u003cb\u003e(0 \u0026lt; u, v \u0026lt; N, u ≠ v, 1 ≤ w ≤ 100)\u003c/b\u003e обозначающее дорогу из \u003cb\u003eu\u003c/b\u003e в \u003cb\u003ev \u003c/b\u003e со стоимостью \u003cb\u003ew\u003c/b\u003e.\u003c/span\u003e\u003c/p\u003e \n "}},{"title":"Output","value":{"format":"HTML","content":" \n \u003cp class\u003d\"MsoNormal\"\u003e\u003cspan class\u003d\"apple-style-span\"\u003e\u003cspan style\u003d\"color:black\"\u003eДля каждого теста выведите номер теста и два числа, означающие максимальное кол-во магазинов, которые мы можем посетить по пути на свадьбу и минимальное время, за которое мы доберемся до места проведения свадьбы, посетив при этом максимальное количество магазинов. Если мы не можем добраться до свадьбы, выведите \u003cb\u003e\"\u003c/b\u003e\u003c/span\u003e\u003c/span\u003e\u003cb\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003eImpossible\"\u003c/span\u003e\u003c/b\u003e\u003cspan class\u003d\"apple-style-span\"\u003e\u003cspan style\u003d\"color:black\"\u003e. Смотрите примеры для лучшего понимания.\u003c/span\u003e\u003c/span\u003e\u003c/p\u003e \n "}},{"title":"Sample Input","value":{"format":"HTML","content":" \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e2\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e4 4 4\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e0 1 2 3\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e0 1 10\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e1 3 30\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e0 2 30\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e2 3 5\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e4 4 4\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e0 1 2 3\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e0 1 10\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e3 1 30\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e0 2 30\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e3 2 5\u003c/span\u003e\u003c/p\u003e "}},{"title":"Sample Output","value":{"format":"HTML","content":" \u003cp class\u003d\"msonospacing0\" style\u003d\"margin:0in;margin-bottom:.0001pt\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;;color:black\"\u003eCase 1: 3 35\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003eCase 2: Impossible\u003c/span\u003e\u003c/p\u003e "}}]}