#include <stdio.h>
#include <iostream>
#include <cstring>
const int maxn  = 22;
using namespace std;
int dist[maxn][maxn];
int randArr[maxn];
int opt[maxn],visit[maxn],visit2[maxn];
int steps[maxn];
int n,m;
int dista,dista2,ans;
int opt22[maxn];
long long times = 0;
void dfs2(int a) {
    times++;
    if(times>20000000) return;
    int visitall = 1;
    for(int i = 1; i<=20; i++) {
    	if(randArr[i]<=n-1&&randArr[i]>=2)
        if(visit2[i]==0) {
            visitall = 0;
            visit2[i] = 1;
            opt22[a] = i;
            dfs2(i);
            opt22[a] = 0;
            visit2[i] = 0;
        }
    }
    if(visitall) {
        int dista22 = 0;
        int z = n;
        int i = 0;
        int flag = 1;
        while(opt22[z]) {
            dista22+=dist[z][opt22[z]];
            ++i;
            if(steps[opt22[z]]<=(n-2)/2&&i>(n-2)-(n-2)/2) {
                flag = 0;
                break;
            }
            z=opt22[z];
        }
        if(flag) {
            dista22+=dist[z][1];
            dista2 = min(dista2,dista22);
        }
    }
}
void dfs(int a) {
    times++;
    if(times>20000000) return;
    int visitall = 1;
    for(int i = 1; i<=20; i++) {
    	if(randArr[i]<=n-1&&randArr[i]>=2)
        if(visit[i]==0) {
            visitall = 0;
            visit[i] = 1;
            opt[a] = i;
            dfs(i);
            opt[a] = 0;
            visit[i] = 0;
        }
    }
    if(visitall) {
        memset(visit2,0,sizeof(visit2));
        dista= 0;
        int z = 1;
        int i = 0;
        while(opt[z]) {
            dista+=dist[z][opt[z]];
            steps[opt[z]]  = ++i;
            z=opt[z];
        }
        dista+=dist[z][n];
        if(dista<ans) {
            dista2 = 1e9;
            dfs2(n);
            ans = min(ans,dista+dista2);
        }
    }
}
int main() {
    ans = 1e9;
    cin>>n>>m;
    for(int i = 1; i<=n; i++)for(int j = 1; j<=n; j++) dist[i][j] = 1e9;
    for(int i = 1; i<=n; i++) dist[i][i] = 0;
    for(int i = 1; i<=m; i++) {
        int x,y,z;
        cin>>x>>y>>z;
        x++,y++;
        dist[x][y] = dist[y][x] =z;
    }
    randArr[1] = 5,randArr[2] = 1,randArr[3] = 4,randArr[6] = 15,randArr[7] = 14,randArr[5] = 3,randArr[8] = 19,randArr[9] = 18,randArr[10] = 2;
    randArr[11]  =6,randArr[12] = 7,randArr[13] = 8,randArr[14] = 9,randArr[15] = 10,randArr[16] = 11,randArr[17] = 12,randArr[18] = 13;
    rabdArr[19] = 16,randArr[20] = 20,randArr[4] = 17;
    for(int k = 1; k<=n; k++) {
        for(int i = 1; i<=n; i++) {
            for(int j = 1; j<=n; j++)
                dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
        }
    }
    visit[1] = 1;
    dfs(1);
    cout<<ans;
    return 0;
}