22145번 - Коронация 다국어

Во Флатландии приближается великий праздник! Скоро пройдет коронация ее нового правителя. Как несложно догадаться, коронация пройдет в столице. Все было бы просто, если бы во Флатландии была только одна столица. Однако, есть целых два города, одинаково претендующих на звание столицы, и до самого конца будет неизвестно, в котором из них пройдет праздник. Поэтому, необходимо дать возможность жителям каждой из столиц доехать до другой.

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

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

В первой строке заданы числа n (4 ≤ n ≤ 10⁵), c₁ и c₂ (1 ≤ c₁, c₂ ≤ n, c₁ ≠ c₂) — количество городов во Флатландии и номера столиц.

Далее, в n − 1 строке задано описание дорог. Каждая дорога задается целыми числами a, b и c (1 ≤ a, b ≤ n, a ≠ b, 1 ≤ c ≤ 1000) — номера городов, соединяемых этой дорогой и количество машин, которые смогут по ней проехать до того, как она развалится, соответственно.

Выведите единственное число — максимальное количество машин, которые смогут доехать из одной столицы в другую после постройки не затрагивающей столицы дороги.