• Хромосома
  DNK 

Описание
Хромосома ДНК – это последовательность генов. Пусть дано число N генов на одной хромосоме ДНК и некоторые попарные расстояния между этими генами. Необходимо написать программу, которая найдет порядок расположения генов на хромосоме, не противоречащий заданным попарным расстояниям между генами. Если такой порядок не существует, программа должна сообщить об этом. Замечание: хотя все заданные попарные расстояния строго положительны по условию задачи, расстояния между некоторыми генами в решении могут быть равны нулю; в этом случае порядок расположения этих (совпадающих) генов несущественен.

Задача
Составьте программу DNK, которая вводит исходные данные из текстового ASCII-файла DNA.DAT, находит требуемый порядок и выводит найденный результат в текстовый файл DNA.SOL


Формат входных данных
Исходные данные размещены в в следующем формате: в первой строке файла находится общее количество N (1<N<=100) генов; в каждой следующей строке файла находятся три числа: i, j, k - разделенные пробелами, где целое число k (0<k<=32000) - расстояние между генами i и j (0< i,j<=N).

Формат выходных данных
Результат записывается в файл в виде последовательности номеров генов. Допускаются разделители – пробелы и концы строк. Если вариантов расположения генов несколько, достаточно вывести любой из них.

Пример 1

Пример 2