Задача №1802. Срочное сообщение
Ромин папа работает в стремительно развивающейся корпорации «РосКошки». Сегодня папа решил показать своему сыну свою компанию, ведь он планирует, что со временем все его дети и внуки будут работать в «РосКошках». Рома — мальчик любознательный, поэтому он довольно быстро узнал всё о структуре корпорации.
Всего в «РосКошках» работает N сотрудников, у каждого из которых (кроме президента) есть один непосредственный начальник. Чтобы сотрудники не отвлекались по мелочам, президент запретил им во время работы общаться с кем-либо, кроме своих непосредственных подчинённых и начальника. Поэтому все сообщения сотрудникам приходится передавать через других сотрудников. Пока Рома без дела бродил по коридорам фирмы, он не только узнал для каждого сотрудника, сколько ему требуется минут, чтобы передать сообщение одному из своих подчинённых или начальнику, но и обнаружил, что в этой фирме работает сисадмин, который имеет особый статус: у него нет ни начальников, ни подчинённых, и он может передавать сообщения любому сотруднику фирмы, причём мгновенно. Но при этом, если у сотрудника есть хотя бы один подчинённый, он никогда не подойдёт к сисадмину с просьбой передать сообщение кому-либо. Рома осознал, что только что ему открылся новый способ передачи информации внутри корпорации, поэтому разузнал для каждого сотрудника, не имеющего подчинённых, сколько ему требуется времени, чтобы дойти до сисадмина.
Ромин папа хорошо осознаёт масштабы любопытства своего сына, поэтому, когда ему в очередной раз потребовалось передать своему другу срочное сообщение, он обратился к своему сыну. Помогите Роме минимизировать время, необходимое для передачи папиного сообщения его другу.
В первой строке входного файла содержится единственное целое число \(N\) — количество сотрудников компании без учёта сисадмина (\(2 \le N \le 10^5\)). В следующих \(N\) строках содержится по 3 целых числа \(p_i\), \(b_i\) и \(s_i\) — номер начальника \(i\)-го сотрудника (для президента \(p_i=0\)) и время, необходимое для передачи сообщения от \(i\)-го сотрудника его начальнику и любому подчинённому соответственно. Если у \(i\)-го сотрудника нет подчинённых, то \(s_i\) — время, необходимое \(i\)-му сотруднику, чтобы добраться до сисадмина (\(1 \le p_i \le N\), \(p_i \ne i\), \(1 \le b_i\) , \(s_i \le 10^4\)).
Выведите единственное число — минимальное время, необходимое для доставки сообщения от Роминого папы (имеющего номер 1) до его друга (имеющего номер \(N\)).