该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

雷厂长是粗粮手机的CEO。粗粮11开卖的第一天，就出现了许多问题。由于野鸡999CPU过于温暖，用户的手机与店内的展示机均出现了许多问题。雷厂长决定将所有故障手机召回维修。

题目描述

给出一个有 $N$ 个城市，$M$ 条公路的地区有权无向图，每个城市都有独立的授权服务中心。求将每个服务点的所有手机送至位于 $1$ 号城市的工厂所需的最短时间。设任意卡车均可一次性带走每个服务中心的所有手机，且速度为 $1$（即所需路程=所需时间）。

格式

输入

输入共有 $N + 1$ 行。

第 $1$ 行有两个整数 $M, N$，分别代表城市数量与公路数量。

第 $2$ 至第 $N + 1$ 行，每行三个整数 $U, V, W$，分别代表两端城市与长度。

输出

一个整数，表示最少所需的时间。

样例

4 6
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

4

限制

$1 \le M, N, U, V \le 10^{4}, 1 \le W \le 300$