Задача №1055. Красная шапочка
В непроходимом лесу имеется N полянок и M тропинок между ними. Каждая тропинка соединяет две различные полянки. Две полянки могут быть соединены несколькими тропинками.
На двух разных полянках живут Красная Шапочка и ее бабушка. Домик Красной Шапочки находится на полянке с номером 1, а домик бабушки - на полянке с номером N. Красная Шапочка хорошо ориентируется в лесу и знает, какое минимальное время ей потребуется для прохождения каждой тропинки. Когда Красная Шапочка идет по лесу, она переходит с тропинки на тропинку только на полянках. На каждой полянке есть укрытие, в котором Красная Шапочка может спрятаться на некоторое время.
В этом же лесу живет Волк. Время, за которое Волк пробегает какую-либо тропинку, может отличаться от времени, за которое по ней проходит Красная Шапочка. Кроме того, если Волк пробегает по одной и той же тропинке несколько раз, то каждый раз он может тратить на это разное время.
С края полянки, где живет Красная Шапочка, Волк увидел, что она собирается нести пирожки бабушке и побежал по тропинкам привычного ему пути от дома Красной Шапочки к дому бабушки. Волк начинает бежать от домика Красной Шапочки в тот момент, когда она решила выйти из дома, его путь заканчивается как только он окажется на полянке с домиком бабушки. Ни на одной полянке Волк не задерживается.
Чтобы застать бабушку в целости и сохранности, Красной Шапочке необходимо обогнать Волка. При этом ей нельзя оказаться с Волком на одной тропинке, даже если Волк уже покидает ее, а она только появляется на ней, или наоборот. Чтобы избежать встречи с Волком на полянке, Красная Шапочка использует имеющееся там укрытие. Красной Шапочке нельзя появляться на полянке одновременно с Волком или покидать укрытие на полянке в тот момент, когда на ней появляется Волк. При необходимости Красная Шапочка может идти по тропинке дольше минимально возможного времени, а также выйти из дома позже, чем она исходно решила.
Необходимо написать программу, которая поможет Красной Шапочке добраться к бабушке раньше Волка, если известна последовательность тропинок, по которым побежал Волк.
Первая строка входного файла содержит числа N, M и K (2 ≤ N ≤ 2000, 1 ≤ M ≤ 100000, 1 ≤ K ≤ 100000). Следующие M строк содержат по три числа: Bi, Ei - номера полянок, которые соединяет i-я тропинка, и Ti - минимальное время, за которое Красная Шапочка может по ней пройти (1 ≤ Ti ≤ 10000). В следующих K строках находится последовательное описание пути Волка, по два числа в строке: Pi - номер тропинки, по которой он побежит, и Vi - время, которое он на это затратит (1 ≤ Vi ≤ 10000). Путь волка всегда начинается на полянке 1 и заканчивается на полянке N. Все числа во входном файле целые и в пределах одной строки разделены пробелами.
В том случае, если Красная Шапочка не может добраться до домика бабушки быстрее Волка, выходной файл должен содержать слово 'NO'.
Если Красная Шапочка сможет добраться до домика бабушки быстрее волка, в первой строке выходного файла должно быть слово 'YES'. Во второй строке в этом случае должно содержаться число тропинок в пути Красной Шапочки. В третью строку следует вывести номера тропинок в том порядке, в котором Красная Шапочка должна по ним пройти. Числа должны быть разделены пробелами.
Информацию о времени прохождения по тропинкам и остановках на полянках в выходной файл выводить не нужно.
\(2 \leq N \leq 200\) Решение оценивается в \(30\) баллов.
\(NK \leq 6 \cdot 10^6\) Решение оценивается в \(40\) баллов.
Дополнительные ограничения отсутствуют. Решение оценивается в \(30\) баллов.
3 2 3 1 2 13 1 3 9 1 5 1 5 2 5
YES 1 2