Несмотря на то, что уже XXI век на дворе, СМИ в Моржландии не сильно распространены. Оповещение городов ведется с помощью гонцов которые могут путешествовать только по дорогам. Сеть дорог в Моржландии устроена так, что от каждого города до любого другого можно добраться ровно одним способом, и длины дорог равны между собой.

Решением правителя Северного Полюса было принято провести информационную реформу. Было решено выбрать несколько городов и назначить их областными центрами. На обслуживание областного центра приходится тратить k рыбликов (местная валюта) в год. Считается, что областной центр всегда имеет информацию о последних новостях.

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

Ваша задача минимизировать расходы на проведение реформы.