# include <fstream>
# include <algorithm>
# include <vector>
# include <queue>
# define inf 999999999
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
struct elem
{
    int y, cost;
}E;
vector <elem> v[50];
struct elem2
{
    int k, past;
}X;
queue <elem2> q;
int i,j,n,m,x,y;
int dist[17][260000];
void back()
{
    int i,k,next,past,cost;
    X.k=0; X.past=0;
    q.push(X);

    while (! q.empty())
    {
        X=q.front(); q.pop();
        k=X.k; past=X.past;

        for (i=0; i<v[k].size(); ++i)
        {
            next=v[k][i].y; cost=v[k][i].cost;
            if (((1<<next)&past)==0)
            {
                if (!dist[next][past+(1<<next)] || dist[next][past+(1<<next)]>dist[k][past]+cost)
                {
                    dist[next][past+(1<<next)]=dist[k][past]+cost;

                    X.k=next; X.past=past+(1<<next);
                    q.push(X);
                }
            }
        }
    }
}
int main ()
{
    f>>n>>m;
    x=1>>0;
    for (i=1; i<=m; ++i)
    {
        f>>x>>y>>E.cost;
        E.y=y; v[x].push_back(E);
        E.y=x; v[y].push_back(E);
    }
    E.y=0; E.cost=0;
    v[n+1].push_back(E);
    back();

    if (!dist[1][(1<<n)-1]) g<<"Nu exista solutie\n";
        else g<<dist[1][(1<<n)-1]<<"\n";
    return 0;
}