#include <iostream>
#include <climits>
#include <algorithm>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <unordered_map>

using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

class disjoint_set{
    vector < int > parent;
    vector < int > sz;

public:
    disjoint_set ( int n ){
        parent.resize( n + 1 );
        for( int i = 1; i <= n; ++i )
            parent[i] = i;
        sz.resize( n + 1 );
        fill(sz.begin(), sz.end(), 1);
    }
    int Find( int x );
    void Union( int x, int y );
};
int disjoint_set::Find( int x ){

    int aux, root = x;
    while( parent[root] != root ) root = parent[root];
    while( parent[x] != x ){
        aux = parent[x];
        parent[x] = root;
        x = aux;
    }
    return root;
}
void disjoint_set::Union(int x, int y){

    int root_x = Find(x);
    int root_y = Find(y);

    if( sz[root_x] >= sz[root_y] ){
        sz[root_x] += sz[root_y];
        parent[root_y] = root_x;
    }
    else{
        sz[root_y] += sz[root_x];
        parent[root_x] = root_y;
    }
}
struct hash_pair {
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const
    {
        auto hash1 = hash<T1>{}(p.first);
        auto hash2 = hash<T2>{}(p.second);
        return hash1 ^ hash2;
    }
};
class graph{
    const int INF = INT_MAX;
    vector< vector < int > > Ad;
    vector< vector < int > > EdgeValue;
    const int nodes;
    int edges = 0;

    void DFSr( int nod, vector < bool > & vis, vector < vector < int > > & ad, vector < int > & comp );
    void DFSdiameter( int nod, int parent, int lg, int& lgmax, int& last );
    void TopoDFS( int nod, vector < bool > & vis, stack < int > & Topo );
    bool BFSflow( int source, int sync, const vector < vector < int > > & AdRes, int** cap, int** flow, int* parent );
    void EulerianCircuitSearch( int nod, vector < vector < pair < int, int > > >& Edge, vector < bool > & Vis, vector < int >& Sol );
public:
    graph( int n):nodes(n){ Ad.resize(nodes+1); EdgeValue.resize(nodes+1); }
    graph( int n, int m, vector < vector < int > > & ad ) : nodes(n), edges(m){
        Ad.resize(nodes+1);
        for( int i = 1; i <= nodes; ++i ){
            for( int j = 0; j < ad[i].size(); ++j)
                Ad[i].push_back(ad[i][j]);
        }
    }
    graph( int n, int m, vector < vector < int > > & ad, vector < vector < int > > & values ) : nodes(n), edges(m){
        Ad.resize(nodes+1);
        EdgeValue.resize(nodes+1);
        for( int i = 1; i <= nodes; ++i )
            for( int j = 0; j < ad[i].size(); ++j){
                Ad[i].push_back(ad[i][j]);
                EdgeValue[i].push_back(values[i][j]);
            }
    }

    int getNodes(){ return nodes; }

    void addEdge(int x, int y, bool oriented, int value );
    void DFS( int nod, bool vis[] );
    void BFS( int nod );
    int ConnectedComponents();
    void Kruskal();
    void Dijkstra( int nod );
    void BellmanFord( int source );
    void TopoSort();
    vector < vector < int > > StronglyConnectedComponents();
    int** RoyFloyd();
    int Diameter();
    int MaxFlow( int source, int sync );
    vector < int > EulerianCircuit( int source );
    int MinimumCostHamiltonianCircuit();
};

void graph::addEdge(int x, int y, bool oriented, int value = INT_MAX ){
    Ad[x].push_back( y );
    if( value != INT_MAX )
        EdgeValue[x].push_back(value);
    if( oriented == false ) {
        Ad[y].push_back(x);
        if( value != INT_MAX )
            EdgeValue[y].push_back(value);
    }
    edges++;
}
void graph::DFS( int nod, bool vis[] ){
    vis[nod] = 1;
    for( int i = 0; i < Ad[nod].size(); ++i ){
        int w = Ad[nod][i];
        if( vis[w] == 0 )DFS(w,vis);
    }
}
void graph::DFSr( int nod, vector < bool > & vis, vector < vector < int > > & ad, vector < int > & comp ){
    vis[nod] = 1;
    comp.push_back( nod );
    for( int i = 0; i < ad[nod].size(); ++i ){
        int w = ad[nod][i];
        if( vis[w] == 0 )DFSr(w, vis, ad, comp);
    }
}
void graph::BFS( int nod ){

    queue < int > Q;

    int dist[nodes+1] = {0};
    Q.push(nod);
    int x;

    while( !Q.empty() ){
        x = Q.front();
        Q.pop();

        for( int i = 0; i < Ad[x].size(); ++i ){
            int w = Ad[x][i];

            if( dist[w] == 0 && w != x && w != nod ){
                dist[w] = dist[x] + 1;
                Q.push(w);
            }
        }
    }

    for( int i = 1; i <= nodes; ++i )
        if( dist[i] != 0 || i == nod )fout << dist[i] << ' ';
        else fout << "-1 ";
}
int graph::ConnectedComponents(){
    int nr = 0;
    bool vis[nodes+1] = {0};
    for( int i = 1; i <= nodes; ++i )
        if( vis[i] == 0 ){
            DFS(i,vis);
            nr++;
        }
    return nr;
}
void graph::Kruskal(){
    struct edge{
        int x, y, v;

        bool operator < ( const edge & E ) {
            return v < E.v;
        }
    };

    vector < edge > E;

    disjoint_set ds(nodes);

    for( int i = 1; i <= nodes; ++i )
        for( int j = 0; j < Ad[i].size(); ++j ){
            E.push_back({i,Ad[i][j],EdgeValue[i][j]});
        }

    sort( E.begin(), E.end() );

    vector < pair < int , int > > Sol;
    int TotalValue = 0, edges_nr = 0;

    for( int i = 0; i < edges && edges_nr < nodes; ++i ){
        int root_x = ds.Find( E[i].x );
        int root_y = ds.Find( E[i].y );
        if( root_x != root_y ){
            edges_nr++;
            Sol.push_back( {E[i].x, E[i].y} );
            TotalValue += E[i].v;
            ds.Union( root_x, root_y );
        }
    }
    fout << TotalValue << '\n';

    fout << Sol.size() << '\n';
    for( int i = 0; i < Sol.size(); ++i )
        fout << Sol[i].first << ' ' << Sol[i].second << '\n';
}
void graph::Dijkstra(int nod){
    priority_queue< pair < int, int >, vector < pair <int, int> >, greater < pair < int, int > >  > H;
    vector < int > dist(nodes+1,INF);
    vector < bool > vis(nodes+1, 0);
    dist[nod] = 0;
    H.push( {0,nod} );

    while( !H.empty() ){
        nod = H.top().second;
        H.pop();

        if( vis[nod] ) continue;
        else vis[nod] = 1;

        for( int i = 0; i < Ad[nod].size(); ++i ){

            int w = Ad[nod][i];
            int dw = EdgeValue[nod][i];

            if( dist[w] > dist[nod] + dw ){
                dist[w] = dist[nod] + dw;
                H.push( { dist[w], w } );
            }
        }
    }

    for( int i = 2; i <= nodes; ++i )
        (dist[i] != INF) ? fout << dist[i] << ' ': fout << 0 << ' ';
}
void graph::BellmanFord( int source ){
    vector < int > dist(nodes+1, INF);
    vector < int > visCount(nodes+1, 0);
    vector < bool > inQ( nodes+1, 0);
    queue < int > Q;

    dist[source] = 0;
    Q.push( source );

    int nod;
    bool negativeCicle = false;

    while( !Q.empty() && !negativeCicle ){
        nod = Q.front();
        Q.pop();
        inQ[nod] = false;

        for( int i = 0; i < Ad[nod].size(); ++i ){
            int w = Ad[nod][i];
            int dw = EdgeValue[nod][i];

            if( dist[w] > dist[nod] + dw ){
                dist[w] = dist[nod] + dw;
                //cout << nod << ' ' << w << ' ' << dist[w] << '\n';

                if( inQ[w] == false ){
                    inQ[w] = true;
                    Q.push( w );
                }

                visCount[w]++;
                if( visCount[w] == nodes ){
                    negativeCicle = true;
                    break;
                }
            }
        }
    }

    if( negativeCicle == true )
        fout << "Ciclu negativ!\n";
    else{
        for( int i = 1; i <= nodes; ++i )
            if( i != source )
                fout << dist[i] << ' ';
        fout << '\n';
    }
}
void graph::TopoDFS( int nod, vector < bool > & vis, stack < int > & Topo ){

    vis[nod] = 1;
    for( int i = 0; i < Ad[nod].size(); ++i ){
        int w = Ad[nod][i];
        if( !vis[w] )
            TopoDFS( w, vis, Topo );
    }
    Topo.push(nod);

}
void graph :: TopoSort(){
    vector < bool > vis(nodes+1, 0);
    stack < int > Topo;

    for( int i = 1; i <= nodes; ++i )
        if( !vis[i] )
            TopoDFS( i, vis, Topo );

    while( !Topo.empty() ){
        fout << Topo.top() << ' ';
        Topo.pop();
    }
}
vector < vector < int > > graph::StronglyConnectedComponents(){
    vector < vector < int > > Ad_r;
    Ad_r.resize(nodes+1);
    for( int i = 1; i <= nodes; ++i )
        for( int j = 0; j < Ad[i].size(); ++j)
            Ad_r[Ad[i][j]].push_back(i);

    stack < int > Topo;
    vector < bool > vis(nodes+1, 0);
    for( int i = 1; i <= nodes; ++i )
        if( !vis[i] )
            TopoDFS( i, vis, Topo );

    vector < vector < int > > scc;
    fill(vis.begin(), vis.end(), 0);
    while( !Topo.empty() ){

        if( !vis[Topo.top()] ){
            vector < int > comp;
            DFSr( Topo.top(), vis, Ad_r, comp);
            scc.push_back( comp );
        }
        Topo.pop();
    }
    return scc;
}
int** graph::RoyFloyd(){

    int** RF = new int* [nodes+1];
    for( int i = 1; i <= nodes; ++i ){
        RF[i] = new int [nodes+1];
        for( int j = 1; j <= nodes; ++j )
            RF[i][j] = INF;
        RF[i][i] = 0;
    }

    for( int i = 1; i <= nodes; ++i )
        for( int j = 0; j < Ad[i].size(); ++j )
            RF[i][Ad[i][j]] = EdgeValue[i][j];

    for( int k = 1; k <= nodes; ++k )
        for( int i = 1; i <= nodes; ++i )
            for( int j = 1; j <= nodes; ++j )
                if( RF[i][j] > (1LL * RF[i][k] + RF[k][j]) )
                    RF[i][j] = RF[i][k] + RF[k][j];

    for( int i = 1; i <= nodes; ++i )
        for( int j = 1; j <= nodes; ++j )
            if( RF[i][j] == INF )
                RF[i][j] = 0;

    return RF;
}
void graph::DFSdiameter( int nod, int parent, int lg, int& lgmax, int& last ){
    if( lg > lgmax ){
        lgmax = lg;
        last = nod;
    }

    for( int i = 0; i < Ad[nod].size(); ++i )
        if( Ad[nod][i] != parent )
            DFSdiameter( Ad[nod][i], nod, lg+1, lgmax, last );
}
int graph::Diameter(){
    int lgmax = 0;
    int last;

    DFSdiameter( 1, 0, 1, lgmax, last );
    lgmax = 0;
    DFSdiameter( last, 0, 1, lgmax, last );

    return lgmax;
}
bool graph::BFSflow(int source, int sync, const vector < vector < int > > & AdRes, int **cap, int **flow, int *parent){
    for( int i = 1; i <= nodes; ++i ) parent[i] = 0;
    queue < int > Q;
    Q.push( source );
    int nod;

    parent[source] = -1;

    while( !Q.empty() ){
        nod = Q.front();
        Q.pop();

        if( nod == sync ) continue;

        for( int i = 0; i < AdRes[nod].size(); ++i ){
            int w = AdRes[nod][i];

            if( !parent[w] && cap[nod][w] - flow[nod][w] > 0 ){
                parent[w] = nod;
                Q.push( w );
            }
        }
    }

    return (parent[sync] != 0);
}
int graph::MaxFlow( int source, int sync ) {
    vector < vector < int > > AdRes;
    AdRes.resize(nodes+1);

    int** cap = new int* [nodes+1];
    int** flow = new int* [nodes+1];
    for( int i = 1; i <= nodes; ++i ){
        cap[i] = new int [nodes+1];
        flow[i] = new int [nodes+1];
        for( int j = 1; j <= nodes; ++j )
            cap[i][j] = flow[i][j] = 0;
    }

    for( int i = 1; i <= nodes; ++i )
        for( int j = 0; j < Ad[i].size(); ++j ){
            AdRes[i].push_back(Ad[i][j]);
            AdRes[Ad[i][j]].push_back(i);
            cap[i][Ad[i][j]] = EdgeValue[i][j];
        }

    int* parent = new int [nodes+1];
    int totalFlow = 0;

    while( BFSflow(source, sync, AdRes, cap, flow, parent) ){

        for( int i = 0; i < AdRes[sync].size(); ++i ){
            int w = AdRes[sync][i];

            if( parent[w] && cap[w][sync] - flow[w][sync] > 0 ){
                parent[sync] = w;
                int flowBottleneck = INF;

                for( int nod = sync; nod != source; nod = parent[nod] )
                    flowBottleneck = min( flowBottleneck, cap[parent[nod]][nod] - flow[parent[nod]][nod] );

                for( int nod = sync; nod != source; nod = parent[nod] ) {
                    flow[parent[nod]][nod] += flowBottleneck;
                    flow[nod][parent[nod]] -= flowBottleneck;
                }
                totalFlow += flowBottleneck;
            }
        }
    }

    for( int i = 1; i <= nodes; ++i ){
        delete [] cap[i];
        delete [] flow[i];
    }
    delete [] cap;
    delete [] flow;
    delete [] parent;

    return totalFlow;
}
vector < int > graph::EulerianCircuit( int source ){
    vector < pair < int, int > > Edges;
    vector < vector < pair < int, int > > > Edge;
    Edge.resize(nodes+1);
    vector < bool > Vis;
    Vis.resize( edges+1 );

    int edgeCount = 0;
    for( int i = 1; i <= nodes; ++i )
        for( int j = 0; j < Ad[i].size(); ++j )
            Edges.push_back({min(i,Ad[i][j]),max(i,Ad[i][j])});
    sort(Edges.begin(), Edges.end() );

    //cout << Edges.size() << '\n';
    for( int i = 0; i < Edges.size(); i +=2 ){
        //cout << i << ' ' << Edges[i].first << ' ' << Edges[i].second << '\n';
        Edge[Edges[i].first].push_back({Edges[i].second, i/2});
        Edge[Edges[i].second].push_back({Edges[i].first, i/2});
        Vis[i/2] = false;
    }
    vector < int > Sol;
    for( int i = 1; i <= nodes; ++i ){
        if( Edge[i].size() == 0 || Edge[i].size()%2 != 0 ){
            Sol.push_back(-1);
            return Sol;
        }}
    EulerianCircuitSearch(source, Edge, Vis, Sol );
    Sol.pop_back();
    return Sol;
}
void graph::EulerianCircuitSearch(int nod, vector<vector<pair<int, int>>> & Edge,
        vector<bool> & Vis, vector<int> & Sol) {
    int w, p;

    while( !Edge[nod].empty() ){
        w = Edge[nod].back().first;
        p = Edge[nod].back().second;
        Edge[nod].pop_back();
        if( Vis[p] == false ){
            Vis[p] = true;
            EulerianCircuitSearch(w, Edge, Vis, Sol );
        }
    }
    Sol.push_back( nod );
}
int graph::MinimumCostHamiltonianCircuit() {
    vector < vector < int > > cost(nodes+1);

    for( int i = 1; i <= nodes; ++i ) {
        cost[i].resize(nodes+1);
        for (int j = 0; j < Ad[i].size(); ++j)
            cost[i][Ad[i][j]] = EdgeValue[i][j];
    }

    vector < vector < int > > dp( (1<<nodes) );
    for( int mask = 0; mask <= (1<<nodes)-1; ++mask ) {
        dp[mask].resize(nodes+1);
        for (int i = 1; i <= nodes; ++i)
            dp[mask][i] = INF;
    }

    dp[1][1] = 0;

    for( int mask = 1; mask <= (1<<nodes)-1; ++mask )
        for( int i = 1; i <= nodes; ++i ){
            if( dp[mask][i] != INF )
                for( int j = 1; j <= nodes; ++j )
                    if( cost[i][j] && !((1<<(j-1)) & mask) )
                        dp[((1<<(j-1)) | mask)][j] = min( dp[((1<<(j-1)) | mask)][j], dp[mask][i] + cost[i][j]);
        }

    long long sol = INF;

    for( int i = 1; i <= nodes; ++i  )
        if( cost[i][1] )
            sol = min(sol, 1LL*dp[(1 << nodes) - 1][i] + cost[i][1] );
    return sol;
}
int main()
{
    int N, M, x, y, z;
    fin >> N >> M;
    graph G(N);
    for( int i = 1; i <= M; ++i ){
        fin >> x >> y >> z;
        G.addEdge(x+1,y+1,1, z);
    }
    int sol = G.MinimumCostHamiltonianCircuit();
    if( sol == INT_MAX )
        fout << "Nu exista solutie\n";
    else fout << sol << '\n';
    return 0;
}