#include <bits/stdc++.h>
//#define dim 2002
using namespace std;
ifstream fin ("hamilton.in");
ofstream fout("hamilton.out");
int n,put[22],dp[19][262145];
const int inf=2000000000;

struct el
{
    int nod,cost;
};
vector<el> a[19],aa[19];

void reconst (int x,int st)
{
    for (auto y:aa[x])
        if ((st&put[y.nod-1])!=0 && dp[y.nod][st-put[x-1]]+y.cost==dp[x][st])
            reconst(y.nod,st-put[x-1]);
    fout<<x<<' ';
}

void rezolva ()
{
    int i,st,sol=inf,x=0;
    for (i=1; i<=n; i++)
        for (st=1; st<=put[n]-1; ++st)
            dp[i][st]=inf;
    dp[1][1]=0;
    for (st=1; st<put[n]-1; st++)
        for (i=1; i<=n; i++)
            if (dp[i][st]!=inf)
                for (auto y:a[i])
                    if ((st&put[y.nod-1])==0)
                        dp[y.nod][st|put[y.nod-1]]=min(dp[y.nod][st|put[y.nod-1]],dp[i][st]+y.cost);
    for (i=1; i<=n; i++)
        if (dp[i][st]!=inf)
            for (auto y:a[i])
                if (y.nod==1 && dp[i][st]+y.cost<sol)
                    sol=dp[i][st]+y.cost,x=i;
    if (sol==inf)
        fout<<"Nu exista solutie";
    else
    {
        fout<<sol;
        fout<<'\n';
    //    reconst(x,put[n]-1); fout<<1<<'\n';
    }
}

int32_t main()
{
    int i,m,x,y,z;
    fin>>n>>m;
    put[0]=1;
    for (i=1; i<=20; i++)
        put[i]=put[i-1]*2;
    for (i=1; i<=m; i++)
    {
        fin>>x>>y>>z;
        x++,y++;
        a[x].push_back({y,z});
        aa[y].push_back({x,z});
    }
    rezolva();
    return 0;
}