#include <vector>
#include <cstdio>

const int INF =10000000;

using namespace std;

vector<int> G[20];
int Cost[20][20];
int n,m;
int dp[262150][20];


/*int min(int a,int b)
{
    if(a>b)
        return a;
    return b;
}
*/

void citire()
{
    int aux;
    int ind;
    int cost;
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            Cost[i][j]=INF;

    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d",&ind,&aux,&cost);
        G[aux].push_back(ind);
        Cost[ind][aux]=cost;
    }

}


void parcurgere()
{
    for(int i=0;i<(1<<n);i++)
        for(int j=0;j<n;j++)
            dp[i][j]=INF;

    dp[1][0]=0;

    for(int i=1;i<(1<<n);i++)
        for(int j=0;j<n;j++)
            if(i & (1<<j))
                for(size_t it=0;it<G[j].size();it++)
                    if(i &(1<<G[j][it]))
                        {
                        dp[i][j]= min(dp[i][j] , dp[i ^ (1<<j)][G[j][it]] + Cost[ G[j][it]][j]);
                        }
    int Sol=INF;

    for(size_t it=0;it<G[0].size();it++)
        Sol = min(Sol,dp[ (1<<n)-1 ][G[0][it]] + Cost[G[0][it]][0]);

    if(Sol==INF)
        printf("Nu exista solutie");
    else
        printf("%d",Sol);

}



using namespace std;

int main()
{
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    citire();
    parcurgere();
    return 0;
}