Задача . E. Железный человек

Тони Старк играет со своими костюмами, которые теперь оснащены автопилотом. Он живёт в Малибу. Малибу представляет из себя n перекрёстков, пронумерованных целыми числами от 1 до n, соединённых с помощью n - 1 двусторонних дорог таким образом, что от любого перекрёстка можно добраться до любого другого, используя данные дороги (да, граф Малибу является деревом).

У Тони есть m костюмов, для каждого из которых разработан специальный план. Костюм номер i появится в момент времени t_i на перекрёстке v_i и будет двигаться в направлении перекрёстка u_i по кратчайшему пути со скоростью c_i дорог в секунду (пересечение перекрёстка происходит мгновенно), а затем исчезнет, как только достигнет перекрёстка u_i. Если костюм достигает перекрёстка u_i непосредственно в момент времени q, то он доступен там в этот момент времени, но не позже. Костюмы передвигаются непрерывно, например, если v_i ≠ u_i, то в момент времени костюм находится на середине дороги. Обратите внимание, что v_i = u_i означает, что костюм будет доступен на перекрёстке v_i только в момент времени t_i и затем исчезнет.

Если в какой-либо момент времени два костюма оказываются в одной точке (это может быть как на перекрёстке, так и на какой-нибудь дороге непосредственно после появления или перед исчезновением), то там происходит взрыв.

Тони просит вас определить момент самого первого взрыва (если это вообще произойдёт).