曦皓去一个国家旅游，共有N个旅游景点，N-1条双向连接的道路将它们联通起来，每一条道路有固定长度。一开始曦皓位于1号景点。

现在希望你能够求出旅行长度最小的方案，使得每个景点至少被访问到一次。

第一行一个整数N，代表景点数目；

接下来N-1行，每行三个整数s、t、w，表示有一条从s到t的双向道路，长度为w，s和t的编号从1开始。

一行一个整数，代表能够访问每个景点至少一次的方案的最小旅行长度。

【样例输入】

样例1：

3

1 2 3

2 3 3

样例2：

3

1 2 3

1 3 3

【样例输出】

样例1：

6

样例2：

9

对于30%的数据，1 ≤ N ≤ 10；

对于70%的数据，1 ≤ N ≤ 1000；

对于100%的数据，1 ≤ N ≤ 50000，1 ≤ w ≤ 1000。