Untitled

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define int long long
#define fi first
#define se second
#define pii pair<int, int>
#define pb push_back
#define vi vector<int>
#define bit(i, x) ((x >> i) & 1)
#define ALL(x) x.begin(), x.end()
#define REP(i, n) for (int i = 1; i <= n; ++i)
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define FORD(i, a, b) for (int i = a; i >= b; --i)
#define Random(lf, rt) (lf + rand() % (rt - lf + 1))
#define Task "vcycle"

using namespace std;
const int maxn = 2e5 + 7, N = 1e18 + 7, mod = 1e9 + 7;

void ADD(int &x, int y) {
    x += y;
    if (x >= mod) x -= mod;
    if (x < 0) x += mod;
}
void MAXIMIZE(int &x, int y) {
    x = max(x, y);
}
void MINIMIZE(int &x, int y) {
    x = min(x, y);
}

int n, m;
int e[16][16], dp[16][(1 << 15) + 7];

signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }

    cin >> n >> m;
    memset(dp, 0x3f, sizeof dp);
    memset(e, 0x3f, sizeof e);
    REP(i, m) {
        int u, v, w; cin >> u >> v >> w;
        MINIMIZE(e[u][v], w);
        MINIMIZE(e[v][u], w);
    }
    REP(k, n) REP(u, n) REP(v, n) 
        MINIMIZE(e[u][v], e[u][k] + e[k][v]);
    dp[1][1] = 0;
    FOR(mask, 0, (1 << n) - 1) REP(i, n) if (dp[i][mask] < N) {
        REP(j, n) if (i != j) {
            int _mask = mask | (1 << (j - 1));
            MINIMIZE(dp[j][_mask], dp[i][mask] + e[i][j]);
        }
    }
    int maxx = 1e18;
    REP(i, n) MINIMIZE(maxx, dp[i][(1 << n) - 1]);
    if (maxx == 1e18) maxx = -1;
    cout << maxx;

    // mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 
    // cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    return 0;
}