Міцно зв'язаний син гір

Ельдар Богданов, гордий син гір, є сильною людиною. Проте на ньому лежить зобов'язання перед Іваном Метельським зробити так, щоб його день на Зимовій школі 2011 пройшов на найвищому рівні. Серед теоретичного матеріалу, який він викладав, була тема сильно зв'язаних компонент. У реальному житті несподіваною компонентою був Снарк, який запропонував провести «Гран-прі двох столиць», що ще глибше залучило Ельдара.

Попри ці зв'язки, Ельдар ще більше занурився у розв'язання наступної задачі:

Задано орієнтований граф із $n$ вершинами та m_1 ребрами. Відомо, що існують вершини $s$ і $t$ такі, що з $s$ досяжні всі вершини, а $t$ досяжна з усіх вершин. Крім цього, задано ще одну множину з m_2 ребер на тих же вершинах. Кожне ребро з другої множини має цілу вагу.

Необхідно додати деякі ребра з другої множини до графа так, щоб виконувались наступні умови:

• Після додавання ребер граф повинен стати сильно зв'язаним (з будь-якої вершини можна дістатись до будь-якої іншої).

• Сума ваг доданих ребер має бути мінімальною.

Поки Ельдар із завзяттям виконує свої зобов'язання, він просить вас розв'язати цю задачу та повідомити йому про існування розв'язку. Якщо розв'язок існує, обрахуйте потрібні значення.