Увійти і вийти
Молодий пірат Віл Твістер загубив дорогоцінний медальйон, який отримав від батька. Зараз він у руках губернатора Гуза. Оскільки цей медальйон дуже важливий для Віла, він вирішив його викрасти. Його присутність не залишиться непоміченою (він же не ніндзя), тому, щоб збільшити свої шанси на успіх, він скористається покровом ночі. Це означає, що подорож до губернаторського дому буде небезпечною, адже кожен, хто йде через місто вночі, викликає підозру.
Місто заповнене вартовими^1, які стоять на стратегічно важливих перехрестях. Віл не є вправним бійцем, тому покладається на фактор несподіванки та швидкість, щоб пройти повз них. Якщо Віл двічі пройде повз одного і того ж вартового, коли йде до і від губернаторського дому, фактор несподіванки зникне, і вдруге є великий ризик бути спійманим. Тому він не хоче двічі проходити повз одного і того ж вартового.
Подорож починається в гавані, куди він прибуде і звідки відпливе на човні. У нього є карта міста, на якій показані всі місця розташування вартових. Враховуючи, що йому доведеться багато бігти, він хоче знайти найкоротший маршрут до і від губернаторського дому, який не проходить двічі повз будь-якого вартового. Чи можете ви допомогти йому знайти такий шлях?
_______
^1 - вартовий - це стаціонарний охоронець.
Вхідні дані
Перша стрічка містить кількість тестів. Кожен тест має наступний формат:
Перша стрічка містить кількість перехресть n і кількість доріг r (2 ≤ n ≤ 1000, 1 ≤ r ≤ 10000).
r стрічок по три числа a, b і l (1 ≤ a, b ≤ n, 1 ≤ l ≤ 1000), що задають двонаправлену дорогу між перехрестями a і b довжини l.
Стрічка, що містить кількість перехресть S (0 ≤ S ≤ min(N-2, 100)).
Стрічка з S різними цілими числами s_i (2 ≤ s_i < n), що вказують на те, що на перехресті s_i стоїть вартовий.
Перехрестя пронумеровані від 1 до n. Човен Віла знаходиться на перехресті 1, а дім губернатора на перехресті n. Гарантується, що шлях від човна до дому губернатора існує.
Вихідні дані
Для кожного тесту виведіть в окремому рядку найменшу сумарну відстань, яку слід подолати Вілу. Якщо не існує маршруту, що проходить повз кожного вартового не більше одного разу, слід вивести "No safe route" (без лапок).