#include <fstream>
#include <vector>
using namespace std;
ifstream cin("hamilton.in");
ofstream cout("hamilton.out");


const int Inf = 0x3f3f3f3f;
int dp[1<<18][19],pret[19][19];
vector<vector<int > >sirad;
int n,m,x,y,c;
int main()
{
    cin>>n>>m;
    sirad = vector<vector<int> >(n+1);

    for(int i=0;i< 1<<n ; ++i)
        for(int j=0; j < n; ++j)
            dp[i][j] = Inf;
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)
            pret[i][j] = Inf;
    while(m--)
    {
        cin>>x>>y>>c;
        sirad[x].push_back(y);
        pret[x][y] = c;
    }

    dp[1][0] = 0;


    for(int i=0;i<(1<<n);++i)
        for(int j=0;j<n;++j)
            if(i&(1<<j))
                for(auto k : sirad[j])
                    if(!(i&(1<<k)))
                        dp[i|(1<<k)][k] = min(dp[i|(1<<j)][k], dp[i][j] + pret[j][k]);

    int res = Inf;
    for(int i=0;i<n;++i)
        res = min(res,dp[(1<<n)-1][i] + pret[i][0]);
    if(res==Inf)
        cout<<"Nu exista solutie\n";
    else cout<<res<<'\n';
    return 0;
}