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

Для переговоров между некоторыми парами планет существуют двунаправленные каналы связи, каждый из которых характеризуется «временем дозвона» t_i, которое, как правило, занимает несколько часов и значительно превышает время разговора. Всего в галактике n каналов связи, и они объединяют все планеты в единую сеть. Это означает, что с любой планеты u можно дозвониться до любой планеты v, возможно, через некоторые промежуточные планеты v₁, v₂, ..., v_m при помощи существующих каналов между u и v₁, v₁ и v₂, ..., v_m - 1 и v_m, v_m и v. При этом время дозвона с u до v будет равно суммарному времени дозвона задействованных каналов.

Итак, каждому президенту необходимо поговорить по очереди с президентами остальных n - 1 планет. При этом переговоры проходят строго последовательно, и пока переговоры с очередной планетой не завершатся, дозвон до следующей не начинается. Поскольку дело очень срочное, из различных способов дозвона до нужной планеты каждый раз выбирается самый быстрый. Для убеждения другого президента в ценности Галактического Союза не требуется много времени, поэтому время переговоров с каждой планетой можно считать равным времени дозвона до нее. Так как президенты ничего не подозревают о намерениях друг друга, они не учитывают в своих планах, что, например, нужный президент может позвонить сам или уже знать о создающемся Галактическом Союзе из других источников.

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