Description

古代行兵打仗，目的就是攻城掠地。

现在，地图上存在N座城市，你是第一座城市的将领。

你的皇上要求你去攻下其他N-1座城市，并且相信你的实力，给了你足够的兵力，和最精良的部队。

因此，你可以同时对多个城市发起进攻，并且可以非常快速的攻下任意一座城市（即攻城时间忽略不计）

当你攻下一座城市之后，可以直接从该城市派兵（当然，兵力也是最精良且无限的）。

但是，由于军队装备太多，你的部队在两座城市之间的行军速度很慢。现在给出N个城市，和M条城市与城市之间的道路，皇上问你最快需要多久攻下所有的城市。

Input Format

第一行给出两个数$N$，$M$（$1 \le N， M \le 100$）表示地图上存在$N$个城市，$M$条道路。

接下来N行，每行三个整数$U$，$V$，$W$（$1 \le U, V \le N, 1 \le W \le 100$），表示军队从$U$城到$V$城需要花费$W$行军时间。

Output Format

输出一个整数表示攻下所有城市的最短时间。

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

3

Source

1816 Online Judge 10.100.0.232