#include <bits/stdc++.h>
#define INT long long int
using namespace std;
INT n, m, W[20][20], a[50], b[50], w[50], ans = 978654321;
vector<INT> G[20];
void dfs(int x, int y, int z)
{
    if( z > n or y >= ans ) return;
    if( x == n )
    {
        if( ans > y ) ans = y;
        return;
    }
    for(int nt : G[x]) dfs(nt, y+W[x][nt], z+1);
}
int main()
{
    freopen(".8.in","r",stdin);
    freopen(".8.out","w",stdout);
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i = 0 ; i < m ; i++ )
    {
        cin>>a[i]>>b[i]>>w[i];
        G[a[i]].push_back(b[i]);
        G[b[i]].push_back(a[i]);
        if( !W[a[i]][b[i]] ) W[a[i]][b[i]]=W[b[i]][a[i]]= w[i];
        else W[a[i]][b[i]]=W[b[i]][a[i]]=min(W[a[i]][b[i]], w[i]);
    }
    for(int i = 0 ; i < m ; i++ )
    {
        W[a[i]][b[i]] = W[b[i]][a[i]] = w[i]/2;
        dfs(1,0,0);
        W[a[i]][b[i]] = W[b[i]][a[i]] = w[i];
    }
    cout<<ans<<endl;
    return 0;
}