#define INF 0x3f3f3f3f
#define MMAX (1<<18) + 5
#define NMAX 20
#include <fstream>
using namespace std;

ifstream f("hamilton.in");
ofstream g("hamilton.out");

int n, m;
int cost[NMAX][NMAX], dp[NMAX][MMAX], memor[NMAX][MMAX];

void init()
{
    for(int i = 0; i<n; ++i)
        for(int j=0; j<n; ++j)
            cost[i][j] = INF;
}




void read()
{
    int x, y, c;

    f>>n>>m;
    //cost[0][0] = 0;
    init();
    for(int i=0; i<m; ++i)
    {
        f>>x>>y>>c;
        cost[x][y] = c;
    }
}

bool isPow(int j)
{
    int x = 1;
    for(int p = 0; p <=n; ++p)
    {
        if(j == x)
            return 1;
        x *= 2;
    }
    return 0;
}




int solve(int i, int j)
{
    if((1<<i) + 1 == j)
        return cost[0][i];

    if(memor[i][j] != 0)
        return dp[i][j];

    int vmin = INF;
    for(int x=1; x<n; ++x)
        if(cost[x][i] != INF && (j & (1<<x)))
            vmin = min(vmin, solve(x, j-(1<<i)) + cost[x][i]);
    memor[i][j] = 1;
    dp[i][j] = vmin;
    return dp[i][j];
}

///4 3 2 1 0
///0 1 1 0 1


void write()
{
    int vmin = INF;
    for(int x = 0; x < n; ++x)
        if(cost[x][0] != INF)
            vmin = min(vmin, dp[x][(1<<n) - 1] + cost[x][0]);
    g<<vmin;

}


int main()
{
    read();


    int vmin = INF;
    int full = (1<<n)-1;
    for(int x = 1; x < n; ++ x)
        if(cost[x][0] != INF)
            vmin = min(vmin, solve(x, full) + cost[x][0]);

    if(vmin == INF)
        g<<"Nu exista solutie";
    else g<<vmin;
    return 0;
}