В некотором государстве имеется N городов, некоторые из них соединены дорогами,
грузоподъемность мостов на которых ограничена. Между любыми городами есть хотя
бы одна цепочка дорог. Написать алгоритм, определяющий путь между этими
городами (в виде последовательности городов), по которому можно перевезти груз
максимального веса.
Для каждого города задан список городов, связанных с ним дорогой, и список
максимальных значений весов, которые можно провести по соответствующим дорогам.
Первая строка входа содержит количество тестов. Первая строка каждого теста
содержит N - количество городов и M - количество дорог, разделенные пробелом.
Вторая строка теста содержит номера начального города F и конечного города L
на пути (1 <= F,L <= N). M следующих строк этого файла задают дороги; каждая
строка содержит по 3 числа, разделенных пробелами - 2 номера городов, между
которыми проложена дорога, и ее максимальную грузоподъемность. Дорогу можно
проходить в любом направлении с одинаковым грузом. M и N не превосходят 100.
Для каждого теста надо вывести:
1) в первую строку - максимальный груз, который можно провезти между
заданными городами,
2) во вторую строку - количество городов на оптимальном пути, включая
первый и последний,
3) в третью строку - номера городов на оптимальном пути, включая первый
и последний.
Если решений несколько, достаточно найти любое.
