{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"Робин переехал в маленькую деревню и любит навещать одного из своих лучших друзей. Обычно он выбирает более длинный маршрут, потому что ему нравится пейзаж по пути. Он решил выбрать второй по качеству путь, а не самый короткий. Он знает, что должен быть второй по качеству путь.\n\nСельская местность состоит из **R** двусторонних дорог, каждая из которых соединяет два из **N** перекрестков, удобно пронумерованных от **1** до **N**. Робин начинает путь в перекрестке **1**, а его друг находится в перекрестке **N**.\n\nВторой по качеству путь может иметь общие дороги с любыми из самых коротких путей, и он может возвращаться назад, т.е. использовать одну и ту же дорогу или перекресток несколько раз. Второй по качеству путь - это самый короткий путь, длина которого больше, чем у самого короткого пути (т.е. если существует два или более самых коротких пути, то второй по качеству путь - это тот, длина которого больше, чем у них, но не больше любого другого пути)."}},{"title":"Input","value":{"format":"MD","content":"Ввод начинается с целого числа **T (\u0026#8804; 10)**, обозначающего количество тестов.\n\nКаждый тест содержит два целых числа **N (1 \u0026#8804; N \u0026#8804; 5000)** и **R (1 \u0026#8804; R \u0026#8804; 10\u003csup\u003e5\u003c/sup\u003e)**. Каждая из следующих **R** строк содержит три целых числа, разделенных пробелами: **u, v** и **w**, описывающих дорогу, соединяющую перекрестки **u** и **v** и имеющую длину **w (1 \u0026#8804; w \u0026#8804; 5000)**."}},{"title":"Output","value":{"format":"MD","content":"Для каждого теста выведите номер теста и второй по качеству самый короткий путь, как описано выше."}},{"title":"Sample","value":{"format":"MD","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\u003e2\n3 3\n1 2 100\n2 3 200\n1 3 50\n4 4\n1 2 100\n2 4 200\n2 3 250\n3 4 100\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 150\nCase 2: 450\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}