21806번 - Красная Шапочка 다국어

문제

В непроходимом лесу имеется $N$ полянок и $M$ тропинок между ними. Каждая тропинка соединяет две различные полянки. Две полянки могут быть соединены несколькими тропинками.

На двух разных полянках живут Красная Шапочка и ее бабушка. Домик Красной Шапочки находится на полянке с номером 1ドル,ドル а домик бабушки --- на полянке с номером $N$. Красная Шапочка хорошо ориентируется в лесу и знает, какое минимальное время ей потребуется для прохождения каждой тропинки. Когда Красная Шапочка идет по лесу, она переходит с тропинки на тропинку только на полянках. На каждой полянке есть укрытие, в котором Красная Шапочка может спрятаться на некоторое время.

В этом же лесу живет Волк. Время, за которое Волк пробегает какую-либо тропинку, может отличаться от времени, за которое по ней проходит Красная Шапочка. Кроме того, если Волк пробегает по одной и той же тропинке несколько раз, то каждый раз он может тратить на это разное время.

С края полянки, где живет Красная Шапочка, Волк увидел, что она собирается нести пирожки бабушке и побежал по тропинкам привычного ему пути от дома Красной Шапочки к дому бабушки. Волк начинает бежать от домика Красной Шапочки в тот момент, когда она решила выйти из дома, его путь заканчивается как только он окажется на полянке с домиком бабушки. Ни на одной полянке Волк не задерживается.

Чтобы застать бабушку в целости и сохранности, Красной Шапочке необходимо обогнать Волка. При этом ей нельзя оказаться с Волком на одной тропинке, даже если Волк уже покидает ее, а она только появляется на ней, или наоборот. Чтобы избежать встречи с Волком на полянке, Красная Шапочка использует имеющееся там укрытие. Красной Шапочке нельзя появляться на полянке одновременно с Волком или покидать укрытие на полянке в тот момент, когда на ней появляется Волк. При необходимости Красная Шапочка может идти по тропинке дольше минимально возможного времени, а также выйти из дома позже, чем она исходно решила.

Необходимо написать программу, которая поможет Красной Шапочке добраться к бабушке раньше Волка, если известна последовательность тропинок, по которым побежал Волк.

입력

Первая строка входного файла содержит числа $N,ドル $M$ и $K$ (2ドル \le N \le 2,000円,ドル 1ドル \le M \le 100,000円,ドル 1ドル \le K \le 100,000円$). Следующие $M$ строк содержат по три числа: $B_i,ドル $E_i$ --- номера полянок, которые соединяет $i$-я тропинка, и $T_i$ --- минимальное время, за которое Красная Шапочка может по ней пройти (1ドル \le T_i \le 10,000円$).

В следующих $K$ строках находится последовательное описание пути Волка, по два числа в строке: $P_i$ --- номер тропинки, по которой он побежит, и $V_i$ --- время, которое он на это затратит (1ドル \le V_i \le 10,000円$). Путь волка всегда начинается на полянке 1 и заканчивается на полянке $N$.

Все числа во входном файле целые и в пределах одной строки разделены пробелами.

출력

В том случае, если Красная Шапочка не может добраться до домика бабушки быстрее Волка, выходной файл должен содержать слово "NO".

Если Красная Шапочка сможет добраться до домика бабушки быстрее волка, в первой строке выходного файла должно быть слово "YES". Во второй строке в этом случае должно содержаться число тропинок в пути Красной Шапочки. В третью строку следует вывести номера тропинок в том порядке, в котором Красная Шапочка должна по ним пройти. Числа должны быть разделены пробелами.

Информацию о времени прохождения по тропинкам и остановках на полянках в выходной файл выводить не нужно.

제한

힌트