Description

奇奇,一个响亮的名字在ACM界.如今奇奇已经腰缠万贯,飞黄腾达,日子过的是无比的滋润.是什么使他到了如此的地位？如果你要这么问,奇奇会不假思索的告诉你:"ACM! 是ACM让他思维敏捷而缜密,是ACM让他头脑灵活而聪慧,是ACM让他谋事果断而细心......".但每天安逸的生活使得奇奇很是烦闷,由于他小时候梦想着找宝藏,于是奇奇打算去历(zuo)险(si).这不，瞎猫碰上死耗子,还真让他不知从哪得来了一张古老的羊皮书.找个安静隐秘的地方,奇奇打开羊皮卷,内容甚是复杂,不过幸亏奇奇学过ACM,利用早年所学的的图论、计算几何、数论加密等一系列方法终于把羊皮卷还原了,原来是一张古代藏宝图.只见地图上有 n 个可能藏有宝物的地方,这 n 个地方一共有 m 条路, 每条路的两端连通着两个地方,路两两互不相通,每两个地方之间仅存在一条路,路是双向可达的.每条路都有一个凶险值,奇奇不知道具体的凶险值是多少,只知道路越长则凶险值越小,每条路的长度在藏宝图中都有标明.奇奇想去一一探查这 n 个地方,为了使得总的凶险值越小,他想选择尽量少的路能到达这 n 个地方,其次在路尽量少的情况下保证总的凶险值也尽量少,也即他所选择的各个路的距离之和最大.这是一个复杂的问题,奇奇已经力不从心了,于是只好求学弟学妹们帮他找到一个方案满足他的要求,如果你找到了,那么他将会把他所得的藏宝分你一半,否则你就会被陷入绝望的奇奇"嘿嘿嘿".

Format

Input

输入数据有多组,对于每组数据包含若干行.每组数据的第一行有两个数字 n 和 m (0 < n <= 1000, 0 <= m < 1000,000),代表着有 n 个奇奇要去的地方(分别编号为1, 2, ..., n), 这 n 个地方存在 m 条路.紧接着 m 行,每行有三个数 i, j, k, 代表着第 i 号藏宝地到第 j 号藏宝地之间的路的距离为 k (0 < u, v <= n. 0 < w < 100,000), 输入数据保证 n 个地方相互连通.

Output

对于每组输入,在单独的一行输出一个数字,代表着满足奇奇要求的路线中每条路的距离之和.

Samples

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

22

Hint

奇奇要去 4 个地方, 这 4 个地方由 5 条路连通, 选择 1 --> 2, 1 --> 3, 2 --> 4 这三条路将使得总路线最长为 22.