#include <bits/stdc++.h>
using namespace std;
const int N = 30, INF = 0x3f3f3f3f;
int n, m, bestv = INF, minsum = 0;
int g[N][N];
int minv[N];
// 扩展的节点
struct node
{
    // lb: 下界值，cv：当前的价值，d：当前的层数，rcost：剩余未被访问节点的最小花费
    int lb, cv, d, rcost;
    int x[N];
    // 用于有优先级的判断
    bool operator <(const node& t) const
    {
        return lb > t.lb;
    }
    // 构造函数
    node (int d, int cv, int rcost, int lb)
    {
        this->cv = cv, this->d = d;
        this->lb = lb, this->rcost = rcost;
    }
};
int main()
{
    memset(g, 0x3f, sizeof g);
    memset(minv, 0x3f, sizeof minv);
    cin >> n >> m;
    for(int i = 1; i <= m; i ++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        g[x][y] = g[y][x] = z;
    }
    // 计算每个顶点出边的最小值，用于计算下界
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= n; j ++)
        {
            //cout << g[i][j] << " " ;
            minv[i] = min(minv[i], g[i][j]);
        }
        //cout << endl;
    }
    for(int i = 1; i <= n; i ++) minsum += minv[i];

    priority_queue<node> q;
    // 选第1个作为起点，所以根节点为顶点1
    node fa = {1, 0, minsum, INF};
    // 初始化解向量
    for(int i = 1; i <= n; i ++) fa.x[i] = i;
    q.push(fa);
    while(q.size())
    {
        fa = q.top();
        q.pop();
        int d = fa.d + 1;
        // 访问到叶子节点，更新最优解
        if(d == n + 1)
        {
            int v1 = g[fa.x[n]][1];
            if(v1 != INF && fa.cv + v1 <= bestv)
            {
                bestv = fa.cv + v1;
                //for(int i = 1; i <= n; i ++) cout << fa.x[i] << " ";
                //cout << endl;
            }
        }
        else
        {
            // 为子节点的解向量赋值
            for(int i = d; i <= n; i ++)
            {
                int v1 = g[fa.x[d - 1]][fa.x[i]];
                if(v1 != INF)
                {
                    // 选择节点为fa.x[i]，更新子节点相应的值
                    int cv = fa.cv + v1;
                    int rcost = fa.rcost - minv[fa.x[i]];
                    int lb = cv + rcost;
                    if(lb <= bestv)
                    {
                        node t = {d, cv, rcost, lb};
                        for(int j = 1; j <= n; j ++) t.x[j] = fa.x[j];
                        // 两次交换
                        // 第一个交换为子节点的第d个顶点赋值为fa.x[i]
                        // 第二个交换时把子节点重复的顶点去掉
                        swap(t.x[d], fa.x[i]);
                        swap(t.x[i], fa.x[d]);
                        q.push(t);
                    }
                }
            }
        }
    }
    if(bestv == INF) cout << "no Hamilton circuit" << endl;
    else cout << bestv << endl;
    return 0;
}