#include <bits/stdc++.h>

const double PI = 3.14159265358979323846;
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
typedef pair<ll, ll> P;
const ll INF = 10e17;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

std::istream &operator>>(std::istream &in, set<ll> &o) {
    ll a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}


bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);

//const ll mod = 1e10;
//typedef priority_queue<P, vector<P>, greater<P> > PQ_ASK;


vector<ll> bfs(int n, vector<vector<int>> &g) {

    vector<ll> costs(n, INF);
    costs[0] = 0;
    queue<int> q;
    q.push(0);
    while (!q.empty()) {
        int from = q.front();
        q.pop();
        for (int to  : g[from]) {
            if (costs[to] != INF) continue;
            costs[to] = costs[from] + 1;
            q.push(to);
        }
    }
    return costs;
}


bool bfs2(int n, vector<vector<int>> &g) {
    vector<ll> costs(n, INF);
    costs[0] = 0;
    queue<int> q;
    q.push(0);
    while (!q.empty()) {

        int from = q.front();
        q.pop();
        for (int to  : g[from]) {

            ll current_cost = costs[to];
            ll next_cost = costs[from] + 1;

            if (current_cost != INF) {
                if (current_cost % 2 != next_cost % 2) return false;
                continue;
            }
            costs[to] = next_cost;
            q.push(to);
        }
    }
    return true;
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<P> v(m);
    for (P &p : v) cin >> p.first >> p.second, p.first--, p.second--;

    vector<vector<int>> g(n);
    for (P p: v) g[p.first].push_back(p.second);
    for (P p: v) g[p.second].push_back(p.first);

    vector<ll> costs = bfs(n, g);
    bool is_2 = bfs2(n, g);

    if (is_2) {
        ll a = 0;
        for (ll c : costs) if (c % 2 == 0) a++;
        ll b = n - a;
        ll all = a * b;
        ll ans = all - m;
        cout << ans << endl;
        ret();
    }

    ll all = ll(n) * (n - 1) / 2;
    ll ans = all - m;
    cout << ans << endl;
}
%:pragma GCC optimize "-O3"
%:pragma GCC optimize("Ofast")
%:pragma GCC optimize("inline")
%:pragma GCC optimize("fast-math")
%:pragma GCC optimize("unroll-loops")
%:pragma GCC optimize("inline-functions")
%:pragma GCC optimize("no-stack-protector")
%:pragma GCC optimize("inline-small-functions")
%:pragma GCC optimize("inline-functions-called-once")
%:pragma GCC target("sse3","sse2","sse")
#include<bits/stdc++.h>
#define ll long long
#define heap priority_queue
using namespace std;
const ll maxn=15+1;
const ll inf=9e17;
ll ans,sum,dp[maxn][1<<maxn],dis[1<<maxn],g[maxn][maxn],tmp,lim,n,m;
inline ll lowbit(ll x){
	return x&-x;
}
int main()
{
	cin>>n>>m;
	ll u,v,w;
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v>>w;
		--u;
		--v;
		g[u][v]=g[v][u]=w;
		sum+=w;
	}
	lim=(1<<n)-1;
	for(int i=1;i<=lim;i++)
	{
		tmp=log2(lowbit(i));
		dis[i]=dis[i^(1<<tmp)];
		for(int j=0;j<n;j++)
			if(g[tmp][j]&&(i&(1<<j)))
				dis[i]+=g[tmp][j];
	}
	memset(dp,0xc0,sizeof(dp));
	dp[0][1]=0;
	ans=-inf;
	for(int i=1;i<=lim;i++)
	{
		if(!(i&1))
			continue;
		for(int j=0;j<n;j++)
			if(i&(1<<j))
			{
				for(int k=i;k;k=(k-1)&i)
					if(k&(1<<j))
						dp[j][i]=max(dp[j][i],dp[j][i^k^(1<<j)]+dis[k]);
				for(int k=lim^i;k;k-=lowbit(k))
				{
					tmp=log2(lowbit(k));
					if(g[tmp][j]) 
						dp[tmp][i^(1<<tmp)]=max(dp[tmp][i^(1<<tmp)],dp[j][i]+g[tmp][j]);
				}
			}
		if(i&(1<<(n-1)))
			ans=max(ans,dp[n-1][i]);
	}
	cout<<sum-ans<<"\n";
	return 0;
}