树的情况都没过（（

所以不用管最小生成树部分

#include <bits/stdc++.h>
#define lb(x) (x&-x)
#define L(i,j,k) for(int i=(j);i<=(k);++i)
#define R(i,j,k) for(int i=(j);i>=(k);--i)
#define swap(a,b) (a^=b^=a^=b)
#define int long long

using namespace std;
using i64 = long long;

typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
void chmin(int &x, int c) {
	x = min(x, c);
}
void chmax(int &x, int c) {
	x = max(x, c);
}

namespace fast_IO{
#define IOSIZE 100000
int precision=3,POW[10]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};char ibuf[IOSIZE],obuf[IOSIZE],*p1=ibuf,*p2=ibuf,*p3=obuf;
#ifdef ONLINE_JUDGE
#define getchar()((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x)((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch)(ch>47&&ch<58)
#define isspace(ch)(ch<33)
#endif
template<typename T>inline T read(){T s=0;int w=1;char ch;while(ch=getchar(),!isdigit(ch)&&(ch!=EOF))if(ch==45)w=-1;if(ch==EOF)return 0;while(isdigit(ch))s=s*10+ch-48,ch=getchar();return s*w;}template<typename T>inline bool read(T&s){s=0;int w=1;char ch;while(ch=getchar(),!isdigit(ch)&&(ch!=EOF))if(ch==45)w=-1;if(ch==EOF)return 0;while(isdigit(ch))s=s*10+ch-48,ch=getchar();return s*=w,1;}inline bool read(char&s){while(s=getchar(),isspace(s));return 1;}inline bool read(char*s){char ch;while(ch=getchar(),isspace(ch));if(ch==EOF)return 0;while(!isspace(ch))*s++=ch,ch=getchar();*s='\000';return 1;}template<typename T>inline void print(T x){if(x<0)putchar(45),x=-x;if(x>9)print(x/10);putchar(x%10+48);}inline void print(char x){putchar(x);}inline void print(char*x){while(*x)putchar(*x++);}inline void print(const char*x){for(int i=0;x[i];i++)putchar(x[i]);}inline bool read(std::string&s){s="";char ch;while(ch=getchar(),isspace(ch));if(ch==EOF)return 0;while(!isspace(ch))s+=ch,ch=getchar();return 1;}inline void print(std::string x){for(int i=0,n=x.size();i<n;i++)putchar(x[i]);}inline bool read(bool&b){char ch;while(ch=getchar(),isspace(ch));b=ch^48;return 1;}inline void print(bool b){putchar(b+48);}inline bool read(double&x){int a=0,b=0;char ch=getchar();bool f=0;while(ch<48||ch>57){if(ch==45)f=1;ch=getchar();}while(47<ch&&ch<58){a=(a<<1)+(a<<3)+(ch^48);ch=getchar();}if(ch!=46){x=f?-a:a;return 1;}ch=getchar();while(47<ch&&ch<58){b=(b<<1)+(b<<3)+(ch^48),ch=getchar();}x=b;while(x>1)x/=10;x=f?-a-x:a+x;return 1;}inline void print(double x){if(x<0){putchar(45),x=-x;}x=round((long double)x*POW[precision])/POW[precision],print((long long)x),putchar(46),x-=(long long)(x);for(int i=1;i<=precision;i++)x*=10,putchar(x+48),x-=(int)x;}template<typename T,typename...T1>inline int read(T&a,T1&...other){return read(a)+read(other...);}template<typename T,typename...T1>inline void print(T a,T1...other){print(a),print(other...);}struct Fast_IO{~Fast_IO(){fwrite(obuf,p3-obuf,1,stdout);}}io;template<typename T>Fast_IO&operator>>(Fast_IO&io,T&b){return read(b),io;}template<typename T>Fast_IO&operator<<(Fast_IO&io,T b){return print(b),io;}
#define cout io
#define cin io
#define endl '\n'
}using namespace fast_IO;
const int maxn = 3e5 + 10, mod = 998244353;
int n, m, cnt, g[20][20];
struct qwq {
	int u, v, w;
}a[maxn];
int u[maxn], v[maxn], idx, w[maxn], p[maxn];
int gf (int x) {
	return p[x] == x ? x : gf(p[x]);
}
int h[maxn], e[maxn], ne[maxn], idxx;
void add (int a, int b) {
	idxx ++ , e[idxx] = b, ne[idxx] = h[a], h[a] = idxx;
}
int dis[110][110];
void dfs (int u, int F, int yb) {
	dis[yb][u] = dis[yb][F] + 1;
	for (int i = h[u]; i; i = ne[i]) {
		int v = e[i];
		if (v == F) continue;
		dfs (v, u, yb);
	}
} 
int st[maxn], st2[maxn], res = INT_MAX;
void f1 (int x, int p1, int r1) {
	if (x == idx + 1) {
		res = min ({res, r1}); return;
	}
	if (x == 1) {
		for (int i = 1; i <= idx; i ++ ) {
			st[i] = 1, st2[u[i]] = st2[v[i]] = 1;
			f1 (x + 1, u[i], w[i]);
			st[i] = 0, st2[u[i]] = st2[v[i]] = 0;
		} return;
	}
	for (int i = 1; i <= idx; i ++ ) {
		if (!st[i] && (st2[u[i]] | st2[v[i]]) && (!(st2[u[i]] && st2[v[i]]))) {
			bool F = (st2[u[i]] ? 1 : 0);
			st[i] = 1, st2[u[i]] = st2[v[i]] = 1;
			if (r1 + dis[p1][(F ? v[i] : u[i])] * w[i] >= res) continue;
			f1 (x + 1, p1, r1 + dis[p1][(F ? v[i] : u[i])] * w[i]);
			st[i] = 0;
			if (F) st2[v[i]] = 0; else st2[u[i]] = 0;
		}
	}
} 
void f2 (int x, int p1, int r1) {
	if (x == idx + 1) {
		res = min ({res, r1}); return;
	}
	if (x == 1) {
		for (int i = 1; i <= idx; i ++ ) {
			st[i] = 1, st2[u[i]] = st2[v[i]] = 1;
			f2 (x + 1, v[i], w[i]);
			st[i] = 0, st2[u[i]] = st2[v[i]] = 0;
		} return;
	}
	for (int i = 1; i <= idx; i ++ ) {
		if (!st[i] && (st2[u[i]] | st2[v[i]]) && (!(st2[u[i]] && st2[v[i]]))) {
			bool F = (st2[u[i]] ? 1 : 0);
			st[i] = 1, st2[u[i]] = st2[v[i]] = 1;
			if (r1 + dis[p1][(F ? v[i] : u[i])] * w[i] >= res) continue;
			f2 (x + 1, p1, r1 + dis[p1][(F ? v[i] : u[i])] * w[i]);
			st[i] = 0;
			if (F) st2[v[i]] = 0; else st2[u[i]] = 0;
		}
	}
} 

void solve() {
	cin >> n >> m;
	memset (g, 0x3f, sizeof g);
	L (i, 1, n) g[i][i] = 0;
	L (i, 1, m) {
		int a, b, c;
		cin >> a >> b >> c;
		g[a][b] = min(g[a][b], c);
		g[b][a] = min(g[b][a], c);
	} 
	L (i, 1, n) L (j, 1, n)
		if (i != j && g[i][j] != 0x3f3f3f3f)
			a[++ cnt].u = i, a[cnt].v = j, a[cnt].w = g[i][j];
	sort (a + 1, a + 1 + cnt, [](qwq i, qwq j){
		return i.w < j.w;
	});
//	for (int i = 1; i <= cnt; i ++ ) {
//		cout << a[i].u << ' ' << a[i].v << ' ' << a[i].w << '\n';
//	}
	for (int i = 1; i <= n; i ++ ) p[i] = i;
	for (int i = 1; i <= cnt; i ++ ) {
		int U = a[i].u, V = a[i].v;
		int pu = gf(U), pv = gf(V);
		if (pu == pv) continue;
		idx ++, u[idx] = U, v[idx] = V, w[idx] = a[i].w, p[pu] = pv;
	}
	for (int i = 1; i <= idx; i ++ ) {
		add (u[i], v[i]), add (v[i], u[i]);
	}	
	for (int i = 1; i <= n; i ++ )
		dfs(i, 0, i);
	for (int i = 1; i <= n; i ++ )
		for (int j = 1; j <= n; j ++ )
			dis[i][j] -- ;
	f1 (1, 0, 0);
	f2 (1, 0, 0);
	cout << res << '\n';
}

signed main() {
	int T = 1;
	while (T--)solve();
	return 0;
}