#include <fstream>
#define INF 1000000

using namespace std;

void read();
void back_tracking(int k);
void afisare();

int n,m,cmin,total;
int sol[20],solmin[20],use[20];
int c[20][20];

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

int main()
{
    read();
    back_tracking(2);
    afisare();
    return 0;
}

void afisare()
{
    fout<<cmin;
}

void back_tracking(int k)
{
    int i;
    if(total>=cmin)
        return;
    if(k==n+1&&c[sol[n]][sol[1]]!=INF)///daca am terminat o solutie
        {
            cmin=total+c[sol[n]][sol[1]];
            for(i=1;i<=n;i++)
                solmin[i]=sol[i];
        }
    else
    if(k<=n)
        for(i=2;i<=n;i++)
            if(use[i]==0&&c[sol[k-1]][i]!=INF)
            {
                use[i]=1;
                total+=c[sol[k-1]][i];
                sol[k]=i;
                back_tracking(k+1);
                use[i]=0;
                total-=c[sol[k-1]][i];
            }

}

void read()
{
    int i,j;
    int x,y,cost;
    fin>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            c[i][j]=INF;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>cost;
        c[x+1][y+1]=cost;
    }
    sol[1]=1;
    use[1]=1;
    cmin=INF;
}