Фаниль собирается отправиться к бабушке в деревню. Деревня бабушки Фаниля очень далеко от Казани. Возможно, ему придётся ехать на нескольких автобусах. Фаниль знает информацию о всех m автобусах и n станциях в округе. Каждый i-ый автобус едет без остановок от станции ai до станции bi и путь этот длины pi . Автобус едет только в одном направлении. Длиной пути от Казани до деревни Фаниль называет суммарную длину всех путей автобусов, на которых он ехал. При этом если Фаниль доехал до какой-нибудь остановки, он на ней же должен сесть на следующий автобус, пока не доберется до деревни Фанилю найти длину кратчайшего пути из Казани до деревни бабушки. Если таких путей несколько, выберите путь, который состоит из максимального количества пересадок, чтобы Фаниль смог полюбоваться красотой каждой станции.