#include<fstream>
#include<vector>
#include<bitset>
using namespace std;

struct nod
{
    int val,cost;
};

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

int n,m,costminim,C;
vector<nod>v[20];
bitset<20>viz;

inline void Citire()
{
    int i,x;
    nod k;
    fin>>n>>m;
    for (i=1;i<=m;i++)
        {
            fin>>x>>k.val>>k.cost;
            x++;k.val++;
            v[x].push_back(k);
        }
}

inline void DFS(int x,int muchii)
{
    int i,len;
    len=v[x].size();
    for (i=0;i<len;i++)
        if (!viz[v[x][i].val])
            {
                viz[v[x][i].val]=1;
                costminim+=v[x][i].cost;
                DFS(v[x][i].val,muchii+1);
                costminim-=v[x][i].cost;
                viz[v[x][i].val]=0;
            }
        else if (muchii==n-1 && v[x][i].val==1)
                C=min(C,costminim+v[x][i].cost);
}

int main()
{
    Citire();
    viz[1]=1;
    C=1<<30;
    DFS(1,0);
    fout<<C<<"\n";
    return 0;
}