题目描述

给出 $n$ 个点的带权无向连通图，可以随意增加 / 减少一条边边权，代价为边权变化量。要求在操作后任意两个相邻点之间直接相连的边长度等于两点间最短路长度，且不能变成负权，求最小代价。

输入格式

第一行 $n,m$，接下来 $m$ 行描述边，每行三个正整数 $x,y,z$，表示连接 $x,y$ 的边边权为 $z$。没有自环重边。点的下标从 $1$ 开始。

$1\le n\le 15,0\le m\le 105$，边和边权都随机生成，且边权 $\in [1,20]$。

输出格式

输出答案，相对或绝对误差在 $10^{-6}$ 以内。

样例

输入

4 4
1 2 1
2 3 1
3 4 1
1 4 8

输出

5.0000000000000000