#include <fstream>
#include <vector>

using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
vector<int> N,D;
int n,m,old_m,new_m,new_c,x,y,c[18][18],d[131100][17],i,sol;
int main()
{
    f>>n>>m;
    for(;m;m--)
    {
        f>>x>>y;
        f>>c[x][y];
    }
    m=(1<<(n-1))-1;
    for(i=0;i<n-1;i++)
        if(c[n-1][i])
            d[1<<i][i]=c[n-1][i];
    for(old_m=1;old_m<m;old_m++)
    {
        N.resize(0);
        D.resize(0);
        for(i=0;i<n-1;i++)
        {
            if(!((1<<i)&old_m))
                N.push_back(i);
            else
                if(d[old_m][i])
                    D.push_back(i);
        }
        for(auto a:D)
            for(auto b:N)
                if(c[a][b])
                {
                    new_m=old_m|(1<<b);
                    new_c=d[old_m][a]+c[a][b];
                    if(!d[new_m][b])
                        d[new_m][b]=new_c;
                    else
                        d[new_m][m]=min(d[new_m][b],new_c);
                }
    }
    sol=18000010;
    for(i=0;i<n-1;i++)
        if(d[m][i]&&c[i][n-1])
            sol=min(sol,d[m][i]+c[i][n-1]);
    g<<sol;
    return 0;
}