Олимпиады по программированию

olympiads.ru

IV Открытая олимпиада школьников по программированию, 2009/10 учебный год

Задача B. Восстановление графа

В неориентированном связном графе N вершин и M ребер, каждое из которых имеет вес, выражающийся натуральным числом (разные ребра могут иметь как одинаковые, так и разные веса). В графе нет петель (т.е. ребер, ведущих из вершины в нее саму) и кратных ребер (т.е. между любыми двумя вершинами не более одного ребра).

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

В этом графе вычислили длины кратчайших путей между всеми парами вершин и записали их в виде таблицы. В этой таблице число на пересечении i-ой строки j-ого столбца равно длине кратчайшего пути из вершины номер i в вершину номер j.

После этого исходный граф был утерян.

Напишите программу, которая по заданной таблице кратчайших расстояний восстановит какой-нибудь граф, которому эта таблица могла бы соответствовать, либо установит, что графа описанного в условии вида, которому могла бы соответствовать данная таблица, не существует.

Формат входных данных

Вводятся числа N и M, а затем таблица кратчайших расстояний (1 ≤ N ≤ 300, 0 ≤ M ≤ 1000, элементы таблицы кратчайших путей - целые неотрицательные числа, не превышающие 10⁶).

Формат выходных данных

Если такой граф существует, выведите в первой строке сообщение YES, в противном случае - сообщение NO. Если граф существует, то начиная со второй строки выведите M троек чисел, описывающих ребра. Каждое ребро описывается номерами вершин, которые оно соединяет, и весом. Веса всех ребер не должны превышать 10⁶.

Примеры

4 4
0 1 2 5
1 0 3 4
2 3 0 7
5 4 7 0

YES
1 2 1
1 3 2
2 4 4
1 4 5

3 2
0 1 1
1 0 1
1 1 0

NO