Farmer John（以下简称FJ）的农场有一片由柱子和栅栏构成的牛圈。
两个柱子之间可以有一条栅栏连接，但一个柱子可以和多个其他的柱子用栅栏连接。
如果栅栏围成封闭的一圈就可以形成一个牛圈。
奶牛们喜欢在牛圈里绕圈散步。
由于设计不周，有的牛圈周长太短，住在那儿的奶牛向FJ抱怨散不了几步又回到起点了。
FJ决定接受民意，拆掉周长最小的那个小牛圈，就请你用计算机找出这个牛圈。
输入M+1行，第1行两个整数分别是柱子的数量N和栅栏的数量M。我们把这N个柱子的编号为1，2，3……N。
第2到M+1行，每行都是三个整数A，B，L，表示编号A的柱子和B的柱子之间有一条长L的栅栏连接。题目保证可以形成牛圈。2<=N<=100，1<=M<=3000，1<=L<=1000。
输出1个整数，表示周长最短的牛圈的周长。

测试样例：
输入:

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

输出：

11

解释：

1，2，4号柱子组成的牛圈周长最小，为11。

---

由LydiaCCC翻译的英文题面版：点击