#include <fstream>
using namespace std;
#define inf 0x3f3f3f3f

int Cost[18][1<<18];
int C[18][18];
int n,m;

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

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

    for (int i = 1; i < (1<<n); i++)
        for (int j = 0; j < n; j++)
            Cost[j][i] = inf;

    // start from 0
    for (int i = 0; i < n; i++)
        if (C[0][i])
            Cost[i][1<<i] = C[0][i];
        else
            Cost[i][1<<i] = inf;

    int Ans = inf;
    for (int i = 1; i < (1<<n); i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (j == 0 && i != (1<<n)-1) continue;
            if ((1<<j)&i)
            {
                for (int k = 0; k < n; k++)
                {
                    if ((1<<k)&i && C[k][j]) {
                        Cost[j][i] = min(Cost[j][i],Cost[k][i^(1<<j)] + C[k][j]);
                        if (i == (1<<n)-1)
                            Ans = min(Ans,Cost[j][i]);
                    }
                }
            }
        }
    }

    if (Ans == 0x3f3f3f3f) fout << -1;
    else fout << Ans;

}