#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ALL(V) (V).begin(), (V).end()
#define ALLR(V) (V).rbegin(), (V).rend()
// #define DEBUGGING

template <typename T> using V = vector<T>;
template <typename T> using VV = V<V<T>>;
template <typename T, typename U> using P = pair<T, U>;
using ll = int64_t;
using PLL = P<ll, ll>;

template <typename T> const T& var_min(const T &t) { return t; }
template <typename T> const T& var_max(const T &t) { return t; }
template <typename Head, typename... Tail> const Head& var_min(const Head &head, const Tail&... tail) { return min(head, var_min(tail...)); }
template <typename Head, typename... Tail> const Head& var_max(const Head &head, const Tail&... tail) { return max(head, var_max(tail...)); }
template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }
template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }

namespace __init {

struct InitIO {
    InitIO() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
        cout << fixed << setprecision(30);
    }
} init_io;

}

#ifdef DEBUGGING
#include "../debug.cpp"
#else
#define DEBUG(...) 0
#endif

template <typename T>
T make_v(T init) { return init; }

template <typename T, typename... Tail>
auto make_v(T init, size_t s, Tail... tail) {
#define rec make_v(init, tail...)
    return V<decltype(rec)>(s, rec);
#undef rec
}

VV<ll> edges;

pair<ll, bool> dfs(ll now, V<ll> &depth, ll d) {
    PLL ret(1, true);
    depth[now] = d;
    for(ll nxt : edges[now]) {
        if(depth[nxt] != -1) {
            ll d1 = depth[nxt];
            ll d2 = depth[now];
            if((d1 % 2) == (d2 % 2)) ret.second = false;
        } else {
            auto tmp = dfs(nxt, depth, d + 1);
            ll t1;
            bool t2;
            tie(t1, t2) = tmp;
            ret.first += t1;
            ret.second &= t2;
        }
    }
    return ret;
}

int main() {
    ll N, M;
    cin >> N >> M;

    edges.resize(N);
    for(ll i = 0; i < M; i++) {
        ll a, b;
        cin >> a >> b;
        a--;
        b--;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }

    V<ll> depth(N, -1);
    V<pair<ll, bool>> subg;
    ll tcnt = 0, lcnt = 0, ocnt = 0;
    for(ll i = 0; i < N; i++) {
        if(depth[i] != -1) continue;
        auto ret = dfs(i, depth, 0);
        ll s;
        bool tree;
        tie(s, tree) = ret;
        if(s == 1) {
            ocnt++;
        } else {
            subg.emplace_back(s, tree);
            (tree ? tcnt : lcnt)++;
        }
    }

    ll ans = 0;
    for(const auto &ele : subg) {
        ll n;
        bool t;
        tie(n, t) = ele;
        ans += tcnt + lcnt;
        ans += (ll)(t) * tcnt;
        ans += n * ocnt;
    }

    DEBUG(ans);

    ans += N * ocnt;

    cout << ans << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<int,ii> eg;
typedef vector<eg> el;
typedef vector<ii> vii;
typedef vector<vii> al;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
vvi g;
int cs[512][512][4];
const int MN = 17;
const int SH = 8;
int am[MN][MN];
int n;
const int MSK = 1<<15;
const int HL = (1<<SH)-1;
void pre() {
	memset(cs,0,sizeof(cs));
	for(int fm=0;fm<=HL;fm++) {
		for(int sm=0;sm<=HL;sm++) {
			for(int id=0;id<4;id++) {
				ll a = fm,b = sm;
				if(id&2) {
					a <<= SH;
				}
				if(id&1) {
					b <<= SH;
				}
				for(int i=0;i<n;i++) {
					if(!((1<<i)&a)) continue;
					for(int j=0;j<n;j++) {
						if(!((1<<j)&b)) continue;
						cs[fm][sm][id] += am[i][j];
					}
				}
			}
		}
	}
}
ll calc(int a, int b) {
	ll res = 0;
	for(int i=0;i<4;i++) {
		int fm=a,sm = b;
		if(i&2) {
			fm >>= SH;
		} else {fm &= HL;}
		if(i&1) {
			sm >>= SH;
		} else {sm &= HL;}
		res += cs[fm][sm][i];
	}
	return res;
}
ll dp[1<<MN][MN];
int main() {
	int m;
	scanf("%d %d",&n,&m);
	memset(am,0,sizeof(am));
	for(int i=0;i<1<<MN;i++) {
		for(int j=0;j<MN;j++) {
			dp[i][j] = 1e12;
		}
	}
	g.assign(n,vi());
	for(int i=0;i<m;i++) {
		int a,b,c;
		scanf("%d %d %d",&a,&b,&c);
		a--;b--;
		am[a][b] = am[b][a] = c;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	pre();
	dp[1][0] = 0;
	for(int i=0;i<(1<<n);i++) {
		for(int j=0;j<n;j++) {
			for(int k=0;k<g[j].size();k++) {
				int u = g[j][k];
				dp[i|(1<<u)][u] = min(dp[i|(1<<u)][u],dp[i][j]+calc(i&(~(1<<j)),1<<u));
			}
			int mm = 1<<n;
			int msk = ((1<<n)-1)&(~i);
			while(1) {
				mm--;
				mm &= msk;
				if(mm <= 0) break;
				dp[mm|i][j] = min(dp[mm|i][j],dp[i][j]+calc(i&(~(1<<j)),mm));
			}
		}
	}
	printf("%lld\n",dp[(1<<n)-1][n-1]);
}