#include <bits/stdc++.h>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int n, m, x, y, z, nod, configuratia;
vector<pair<int, int>>a[20];
queue<pair<int, int>>q;
pair<int, int>r;
int dp[20][(1<<20)+5];
int main()
{
    fin>>n>>m;
    for (int i=1; i<=19; i++) {
        for (int j=1; j<=(1<<20)+4; j++) {
            dp[i][j]=INT_MAX/2;
        }
    }
    for (int i=1; i<=m; i++) {
        fin>>x>>y>>z;
        x++;
        y++;
        a[x].push_back({y, z});
    }
    dp[1][0]=0;
    q.push({1, 0});
    while (q.empty()==0) {
        r=q.front();
        q.pop();
        nod=r.first;
        configuratia=r.second;
        for (auto i:a[nod]) {
            if (((configuratia>>(i.first))&1)==0) {
                if (dp[i.first][configuratia+(1<<i.first)]>dp[nod][configuratia]+i.second) {
                    dp[i.first][configuratia+(1<<i.first)]=dp[nod][configuratia]+i.second;
                    q.push({i.first, configuratia+(1<<i.first)});
                    cout<<i.first<<' '<<configuratia+(1<<i.first)<<'\n';
                }
            }
        }
    }
    fout<<dp[1][(1<<(n+1))-2];
    return 0;
}