#include <fstream>

using namespace std;

ifstream cin("hamilton.in");
ofstream cout("hamilton.out");

const int INF = 1e9;
int dp[1 << 20][20],n,m,cost[20][20];

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



    for(int mask = 0; mask<(1<<n); mask++)
        for (int j = 0; j < n; j++)
        {
            dp[mask][j] = INF;
        }

    dp[1][0] = 0;
    for(int mask = 1; mask<(1<<n); mask++)
        for(int comingfrom = 0;comingfrom < n;comingfrom++)
    {
        if(!(mask & (1<<comingfrom))) continue;//nodul din care pornim spre urmatorul nu este in configuratie;
        if(dp[mask][comingfrom] == INF) continue;//

        for(int nextnode = 0;nextnode < n;nextnode++)
        {
            if(cost[comingfrom][nextnode] && !(mask & (1 << nextnode)))//am muchie si daca pot adauga nodul(nu a fost deja selectat)
            {
                dp[mask | (1 << nextnode)][nextnode] = min(dp[mask | (1 << nextnode)][nextnode],dp[mask][comingfrom] + cost[comingfrom][nextnode]);
            }
        }
    }
    int bestsum = 1e9;

    for(int i=0;i<n;i++)
            if(cost[i][0])
                bestsum = min(bestsum,dp[(1<<n)-1][i] + cost[i][0]);

    cout<<bestsum;

    return 0;
}