Description

约翰的农场有N（1≤N≤1000）块田地，编号为1到N。第1块田地上有他的房子，第N块田地上有一个大谷仓。有M（1≤M≤10000）条道路连接田地，每条道路都连接了两个不同的田地，并且长度大于0小于35000。他从家开始，可能穿过一些田地，最后到谷仓。后来，他又回到家里。他希望自己的旅程尽可能短，但不想经过任何一条道路超过一次。

Format

Input

第1行包含两个整数N和M。第2..M+1行，每行都包含一条路径的3个整数：起始田地、结束田地和道路长度。

Output

单行输出最短行程的长度。

Samples

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

6