Кодер ZS нарисовал неориентированный граф из n вершин пронумерованных от 0 до n - 1 и m ребер между ними. Каждое ребро графа взвешено, а каждый вес — целое положительное число.
На следующий день Кодер ZS обнаружил, что некоторые из весов были стерты! Теперь он хочет восстановить целый положительный вес у каждого ребра, вес которого был стерт, так, что длина кратчайшего пути между вершинами s и t в получившемся графе в точности равна L. Поможете ему?
Выходные данные
Выведите «NO» (без кавычек) в единственной строке, если восстановить веса ребрам требуемым образом невозможно.
В противном случае, выведите «YES» в первой строке. Следующие m строк должны содержать описания ребер получившегося графа, с весами, заданными ребрам, вес которых был стерт. i-ая из них должна содержать три целых числа ui, vi и wi, означающих ребро между ui и vi веса wi. Ребра нового графа должны совпадать с ребрами графа из входных данных. Веса, которые не были стерты, должны остаться неизменными, тогда как новые веса могут быть любыми целыми положительными числами, не превышающими 1018.
Порядок ребер в выходных данных не важен. Длина кратчайшего пути между s и t должна равняться L.
Если существует несколько решений, выведите любое из них.
Примечание
Вот так выглядит граф в первом примере из условия:
В первом примере из условия вес отсутствует всего у одного ребра. Если задать ему вес, равный 8, то длина кратчайшего пути между 0 и 4 будет равна 13.
Во втором примере из условия всего одно ребро. Очевидно, единственным ответом является задание ему веса 123456789.
В последнем примере из условия ни один вес задавать не нужно, но длина кратчайшего пути не совпадает с нужным значением, так что ответ — «NO».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 5 13 0 4
0 1 5
2 1 2
3 2 3
1 4 0
4 3 4
|
YES
0 1 5
2 1 2
3 2 3
1 4 8
4 3 4
|
|
2
|
2 1 123456789 0 1
0 1 0
|
YES
0 1 123456789
|
|
3
|
2 1 999999999 1 0
0 1 1000000000
|
NO
|