#include <fstream>
#define INF 20000000
#define NMAX 30
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

int C[NMAX][NMAX],sol[NMAX],solmin[NMAX],uz[NMAX];
int cost,costmin=INF,n,m;

void citire();
void bkt(int k);


int main()
{
    citire();
    sol[1]=1;
    uz[1]=1;
    bkt(2);
    fout<<costmin-1;
    return 0;
}



void bkt(int k)
{
    if(k==n+1)
    {
        if(cost+C[sol[1]][sol[n]]<costmin)
        {
            for(int i=1;i<=n;i++)
                solmin[i]=sol[i];
            costmin=cost+C[sol[1]][sol[n]];
        }
        return;
    }
    for(int i=2;i<=n;i++)
    {
        if(!uz[i]&&C[sol[k-1]][i]!=INF&&i!=sol[k])
        {
            sol[k]=i;
            uz[i]=1;
            cost+=C[sol[k-1]][i];

            bkt(k+1);

            sol[k]=0;
            uz[k]=0;
            cost-=C[sol[k-1]][i];
        }
    }
}


void citire()
{
    fin>>n>>m;
    int x,y,c,i,j;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
            C[i][j]=INF;
        C[i][i]=0;
    }
    for(i=0;i<m;i++)
    {
        fin>>x>>y>>c;
        x++;y++;
        C[x][y]=c;
    }
}