Description

在n个村庄建造公路，要求任意两个村庄间能相互到达，求最少需要建多长的公路。

Input

多组测试数据。每组测试数据，第一行输入两个整数n(2<=n<=10000)和m （1<=m<=20000 且m <= n*(n-1）/2)。第2到m+1行，每行输入s（1<=s<=n）且t（1<=t<=n）。

Output

每组数据输出一行，表示最少需要建的公路的长度。

Sample Input

3 3
1 2 4
2 3 10
1 3 5

Sample Output

9

HINT

Source