Re的故事之Re表白

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

Re看上了一个妹子,为了不透露信息我们暂且称之为CC是一个很内向的妹子,所以Re这次表白不想惊动任何一个人,所以,苦逼的Re只能自己在几个表白点来回赶,来准备表白所需要的一切事项,但是,妹子眼看就要到地方了,咱们得选最快的速度来检查现场;

已知从u点到vRe需要走w分钟;问,Re需要找一套路线这个路线能够让每一个点都可达到,求这个路线的最短总距离;

 

Input

第一行输入两个整数n,m,分别表示点的数量和路的数量其中( 0 <  n <= 300,0 < m <= 10000 )

接下来m行每行输入三个整数u,v,w,表示从uv需要花w分钟。(0 <= u ,v < n, 1 <= w <= 10000 )

Output

 Re最少需要多少分钟,能够遍历每一个。

Sample Input

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

Sample Output

4

Hint

 

Source

flyfire