sng summer camp 6

闻闻薰衣草的香味，就可以知道情人有多爱你。
与其说薰衣草是开在田野中大片大片的紫，飘在空中的香，不如说是记忆里的东西。
收割薰衣草，如同收割幸福的爱情。
陶醉在紫色的花海中，爱情如此甜蜜。
风起的时候，薰衣草的味道总会飘近身边。
阳光下的香味，弥漫着思念。
记忆就象薰衣草，一起走过的爱情不能忘。
——英国民谣《薰衣草》（节选）

hcy226 带着他的女朋友来到了法国美丽的普罗旺斯，顺着这美丽的薰衣草的花海，他们准备游览 $N$ 个不同的城市。

这 $N$ 个城市之间一共有 $N-1$ 条道路。他们此时在最北边的一座城市，准备在玩一遍所有的城市之后，再回到最北边的那一座城市。数据保证每个城市都是可以到达的。（编号为 1 的城市为最北方的城市）

他们希望这一次的旅行不要浪费太多的时间在路上，所以请你帮他们算一算，游玩这么多城市在路上最少需要消耗多少时间。