666

include <bits/stdc++.h>
using namespace std;
const int Max=5000;
const int inf=1e9;
int n,m,ans=1e9,tot;
int dis[20][20],f[20][Max];
int p[Max],num[Max],pos[Max],sum[Max],condition[Max];
inline int get_int(){
    int x=0,f=1;
    char c;
    for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar());
    if(c=='-'){f=-1;c=getchar();}
    for(;isdigit(c);c=getchar()){
        x=(x<<3)+(x<<1)+c-'0';
    }
    return x*f;
}
inline int mn(int x,int y){
    return x<y?x:y;
}
int main(){
    n=get_int(),m=get_int();
    memset(f,0x3f,sizeof(f));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            dis[i][j]=10000000;
        }
    }
    for(int i=1;i<=m;i++){
        int x=get_int()-1,y=get_int()-1,z=get_int();
        dis[x][y]=dis[y][x]=mn(z,dis[x][y]);
    }
    for(int i=0;i<n;i++){
        pos[1<<i]=i,f[0][1<<i]=0;
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<(1<<n);j++){
            tot=0;
            for(int to=0;to<n;to++){
                if((1<<to)&j){
                    continue;
                }
                p[tot]=1<<to;
                num[tot]=10000000;
                for(int k=j;k;k-=k&(-k)){
                    int from=pos[k&(-k)];
                    num[tot]=mn(num[tot],dis[from][to]*(i+1));
                }
            tot++;
            }
            for(int k=1;k<(1<<tot);k++){
                condition[k]=condition[k-(k&(-k))] | p[pos[k&(-k)]];
                sum[k]=sum[k-(k&(-k))] + num[pos[k&(-k)]];
                f[i+1][j|condition[k]]=mn(f[i+1][j|condition[k]],f[i][j]+sum[k]);
            }
        }
    }
    for(int i=0;i<=n;i++){
        ans=mn(ans,f[i][(1<<n)-1]);
    }
    cout<<ans<<"\n";
    return 0;
}