#include <bits/stdc++.h>
#define pii pair<int, int>
#define MAXN 1001
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");
vector<vector<pii>> mat(MAXN);
vector<vector<bool>> vis(MAXN);
int MIN = INT_MAX, n, m;
void Ddfs(int np, int na, int val, int start){
    //cout << na+1 << " (" << val << ")\n";
    if(val != mat[np][na].second && na == start){
        MIN = min(MIN, val);
        //cout << "Aggiornato min : "<< MIN << "\n";
        return;
    }
    if(MIN <= val) return;
    for(int j = 0; j < mat[na].size(); j++)
        if(!vis[na][j]){
            int dest;
            for(int k = 0; k < mat[mat[na][j].first].size(); k++)
                if(mat[mat[na][j].first][k].first == na)
                    dest = k;
            vis[na][j] = true;
            vis[mat[na][j].first][dest] = true;
            Ddfs(na, mat[na][j].first, val + mat[na][j].second, start);
            vis[na][j] = false;
            vis[mat[na][j].first][dest] = false;

        }
}
int main(){
    in >> n >> m;
    for(int j = 0; j < m; j++){
        int a, b, c;
        in >> a >> b >> c; a--;b--;
        mat[a].push_back({b, c}); vis[a].push_back(false);
        mat[b].push_back({a, c}); vis[b].push_back(false);
    }
//  for(auto &row : mat){
//      for(auto &cell : row) cout << cell.first+1 << " ";
//      cout << endl;
//  }
    for(int i = 0; i < 1 /*n*/; i++)
        for(int j = 0; j < 1/*mat[i].size()*/; j++){
            //cout << i+1 << "-> " << mat[i][j].first+1 << "|\n";
            int dest;
            for(int k = 0; k < mat[mat[i][j].first].size(); k++)
                if(mat[mat[i][j].first][k].first == i)
                    dest = k;
            vis[i][j] = true;
            vis[mat[i][j].first][dest] = true;
            Ddfs(i, mat[i][j].first, mat[i][j].second, i);
            vis[i][j] = false;
            vis[mat[i][j].first][dest] = false;

        }
    //cout << MIN;
    out << MIN;
    return 0;
}