/**
 * @brief 巡回セールスマン問題(traveling-salesman problem)を扱います
 *
 * @note  巡回セールスマン問題はハミルトン閉路問題に密接に関連した問題で、セールスマンはn個の都市を訪問しなければならない
 *        この問題をn個の頂点を持つ完全グラフとして定式化すると、各都市を正確に1回だけ訪れ、最初に出発した都市で終わる巡回路(tour)
 *        あるいはハミルトン閉路を構成することがセールスマンの目的であるが、都市iから都市jに移動するのに非負整数のコストc(i, j)が
 *        かかるので、全コストが最小になるようにしたいというのがセールスマンの希望である. ここで、全コストは巡回路の辺に
 *        割り当てられていたコストの総和である
 *
 * @note  巡回セールスマン問題はNP完全であり、多項式時間の効率的なアルゴリズムは知られていない. しかし、動的計画法を用いることで
 *        ある程度nが小さいサイズならば、厳密解を与えることができる
 *
 * @note  関連URL: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_A
 * @date  2016/05/08
 */



//********************************************************************************
// 必要なヘッダファイルのインクルード
//********************************************************************************

#include <vector>
#include <algorithm>
#include <iostream>



//********************************************************************************
// オブジェクト形式マクロの定義
//********************************************************************************

#define GRAPH_BEGIN namespace graph {
#define GRAPH_END   }



//********************************************************************************
// 名前空間の始端
//********************************************************************************

GRAPH_BEGIN



//********************************************************************************
// 型シノニム
//********************************************************************************

using weight_t   = std::int32_t;  /**< 辺(u, v)への重みwを表す型 */
using index_t    = std::int32_t;  /**< 頂点vの添字を表す型       */
using capacity_t = weight_t;      /**< 辺(u, v)の容量を表す型    */
using bool_t     = std::int32_t;  /**< ブール値は整数型で、{ false 0 true それ以外 }とする */



//********************************************************************************
// 構造体の定義
//********************************************************************************

/**
 * @brief  頂点色列挙構造体(scoped enum)
 * @detail (u, v) ∈ Eで頂点uが黒ならば頂点vは灰か黒である
 *         すなわち、黒頂点に隣接する全ての頂点は発見済みである
 *         灰頂点は白頂点に隣接することがあり、これらの頂点が既発見頂点と未発見頂点の境界をなす
 */
enum struct vcolor : std::int32_t {
    white,  /**< 未発見頂点 */
    black,  /**< 既発見頂点 */
    gray,   /**< 既見済頂点 */
};

/**
 * @brief グラフ用ノード(頂点) 
 */
struct vertex {
    union {
        weight_t d;       /**< 始点sからの距離  */
        weight_t key;     /**< Primのアルゴリズムにおいて木に属するある頂点とを結ぶ重み */
    };
    index_t pi;           /**< 先行頂点(の添字) */
    union {
        vcolor color;     /**< 頂点の色        */
        bool_t  visited;  /**< 発見済みか?     */
    };
    // weight_t f;           /**< 終了時刻印(DFSにおいて、黒色に彩色されたとき、刻まれる)     */
    vertex() : d(0), pi(0), color(vcolor::white)/*, f(0)*/ {}
};

/**
 * @brief グラフ用エッジ(辺)
 * @note  G = (V, E)を重み関数wを持つ重み付きグラフとすると、
 *        辺(u, v) ∈ Eの重みはw(u, v)と表される
 */
struct edge {
    index_t  src;   /**< 辺の始点u */
    index_t  dst;   /**< 辺の終点v */
    union {
        weight_t w;     /**< 辺(u, v)への重み(コスト) */
        capacity_t c;   /**< 辺(u, v)の容量 */
    };
    edge() = default;
    edge(index_t src, index_t dst) : src(src), dst(dst), w(1) {}
    edge(index_t src, index_t dst, weight_t w) : src(src), dst(dst), w(w) {}
};



namespace limits {
    enum {  // scopedではあるが強く型付けされたenum(strongly-typed enum)ではない
        inf = std::numeric_limits<weight_t>::max() / 3,  /**< @brief 辺が存在しない場合に使用される値     */
        nil = std::numeric_limits<index_t>::min() / 3,   /**< @brief 先行点が存在しない場合に使用される値 */
    };
}



//********************************************************************************
// 型シノニムその2
//********************************************************************************

using edges_t    = std::vector<edge>;      /**< グラフG=(V, E)の辺集合E   */
using vertices_t = std::vector<vertex>;    /**< グラフG=(V, E)の頂点集合V */
using array_t    = std::vector<weight_t>;  /**< 重みwの配列  */
using indices_t  = std::vector<index_t>;   /**< 頂点の添字配列 */
using stamps_t   = std::vector<bool_t>;    /**< ブーリアンの集合 */
using matrix_t   = std::vector<array_t>;   /**< グラフGの隣接行列表現(および表行列表現) */
using graph_t    = std::vector<edges_t>;   /**< グラフGの隣接リスト表現(こちらを主に使用する) */



//********************************************************************************
// 型シノニムその3
//********************************************************************************

using vset_t = std::int64_t;  // 頂点集合のビット表現



//********************************************************************************
// 関数の定義
//********************************************************************************

/**
 * @brief 履歴管理法によって巡回セールスマン問題に厳密解を与えます
 *
 * @param vset_t  S    最小重みが決定された頂点集合S(ビット表現)
 * @param index_t u    現在探索している頂点u
 * @param const matrix_t& W  隣接行列W
 * @param matrix_t& D  uにいる状態から残りすべての頂点を辿って始点s(=0)に戻る閉路の重みの総和の最小値をD[S][u]に格納した行列D
 */
weight_t lookup_tsp(vset_t S, index_t u, const matrix_t& W, matrix_t& D)
{
    // 訪問済みなら返ります
    if (D[S][u] >= 0) { return D[S][u]; }

    // すべての頂点を訪れて戻ってきた
    index_t n = W.size();
    if ((S == ((1 << n) - 1)) && u == 0) { return D[S][u] = 0; }

    weight_t d = limits::inf;  // uにいる状態から残りすべての頂点を辿って始点に戻る閉路の重みの総和の最小値をdとする
    
    for (index_t v = 0; v < n; v++) {       // 次の状態vを探索
        if ((S >> v) & 0x01) { continue; }  // 訪問済みならcontinue
        d = std::min(d, (lookup_tsp((S | (1 << v)), v, W, D) + W[u][v]));  // dの更新
    }
    return D[S][u] = d;
}


/**
 * @brief 履歴管理法によって巡回セールスマン問題に厳密解を与えます
 *
 * @param  index_t s    始点s
 * @param  const matrix_t& W  隣接行列W
 * @return 最短ハミルトン閉路Hの最小重み
 */
weight_t memoized_tsp(index_t s, const matrix_t& W)
{
    std::size_t n = W.size();            // n = W.rows
    matrix_t D(1 << n, array_t(n, -1));  // Dを2^n x n型の新しい行列とする

    return lookup_tsp(0, s, W, D);
}


/**
 * @brief トップダウン方式の動的計画法により巡回セールスマン問題に厳密解を与える
 *
 * @param index_t s  始点s
 * @param const matrix_t& W  隣接行列W
 * @return 最短ハミルトン閉路Hの最小重み
 */
weight_t top_down_tsp(const matrix_t& W)
{
    index_t n = W.size();                         // n = W.rows
    matrix_t D(1 << n, array_t(n, limits::inf));  // Dを2^n x n型の新しい行列とする

    D[(1 << n) - 1][0] = 0;  // 始点s(=0)の初期化

    for (vset_t S = (1 << n) - 2; S >= 0; S--) {
        
        for (index_t u = 0; u < n; u++) {
            
            for (index_t v = 0; v < n; v++) {    
                if ((S >> v) & 0x01) { continue; }  // 訪問済みならば、continue
                D[S][v] = std::min(D[S][v], D[(S | (1 << v))][u] + W[u][v]);  // Dの更新
            }
        }
    }
    return D[0][0];
}



//********************************************************************************
// 名前空間の終端
//********************************************************************************

GRAPH_END



//********************************************************************************
// エントリポイント
//********************************************************************************

int main()
{
    using namespace std;

    using namespace graph;

    index_t V, E;
    cin >> V >> E;

    matrix_t W(V, array_t(V, limits::inf));
    for (index_t i = 0; i < V; i++) { W[i][i] = 0; }

    index_t s, t;
    weight_t d;
    for (index_t i = 0; i < E; i++) {
        cin >> s >> t >> d;
        W[s][t] = d;
    }

    d = top_down_tsp(W);
    if (d >= limits::inf) { cout << -1 << endl; }
    else { cout << d << endl; }

    return 0;
}

Measured memory_bytes: 6204