#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>
#include <climits>
#include <algorithm>
#define MAXN 1005
using namespace std;

typedef pair<int,int> ii;
typedef vector<ii> vi;
vi G[MAXN];
int N, M, dist[MAXN], prec[MAXN], minimo=INT_MAX;
bool precU[MAXN], vis[MAXN];

int main(){
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    cin >> N >> M;
    for(int i=0, u, v, w; i<M; i++){
        cin >> u >> v >> w;
        G[u].push_back( make_pair(w, v) );
        G[v].push_back( make_pair(w, u) );
    }

    priority_queue< ii, vi, greater<ii> > Q;
    fill_n(dist, N+1, INT_MAX);
    fill_n(prec, N+1, N);
    dist[0]=prec[0]=0;
    for(int nd=1; nd<=N; nd++){ //trova il prossimo nodo da cui far partire Dijkstra
        if(vis[nd]) continue;
        dist[nd] = 0; //distanza iniziale a 0
        Q.push( make_pair(0, nd) ); //inserisco il nodo di partenza nell'heap
        prec[nd] = 0; //precedente iniziale a 0
        while(!Q.empty()){
            int u = Q.top().second; Q.pop(); //prendo il nodo da visitare
            if(vis[u]) continue; //se l'ho già visitato salto al prossimo

            for(int i=0; i<G[u].size(); i++){ //vedo i nodi connessi ad "u"
                int v = G[u][i].second, w = G[u][i].first;
                if( vis[v] && v!=prec[u]){ //se ce n'è uno che è già visitato ma non è il predecessore, vedo se può essere un ciclo minimo

                    //Trovo il predecessore comune
                    fill_n(precU, N+1, false);

                    int p = prec[u], d;
                    while(p>0){
                        precU[p]=true;
                        p = prec[p];
                    }
                    p = v;
                    while(p>0 && !precU[p])
                        p = prec[p];
                    //ora il predecessore comune sarà "p"

                     //la lunghezza del ciclo sarà la DistanzaDaPadU + DistanzaDaPaV + ArcoDaUaV
                    d = dist[u]-dist[p] + dist[v]-dist[p] + w;

                    minimo = min(d, minimo);
                }

                if( w+dist[u] < dist[v]){ //Classico controllo di Dijkstra
                    dist[v] = w+dist[u];
                    prec[v] = u;
                    Q.push( make_pair(dist[v], v) );
                }
            }

            vis[u] = true; //segno il nodo come visitato
        }
    }

    cout << minimo << "\n";
    return 0;
}