#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n , m;
map<int , pair<ll,ll> > E[300005];
const ll inf = 1e18 + 1;
void adde(int u,int v,ll w) {
    if(E[u].count(v)) {
        E[u][v].first = min(E[u][v].first , (ll)w) ;
    }
    else {
        E[u][v] = {w , inf} ;
    }
    if(E[v].count(u)) {
        E[v][u].second = min(E[v][u].second , (ll)w) ;
    }
    else {
        E[v][u] = {inf , w};
    }
}
void remov(int u,int v) {
    E[u].erase(v) ;
}
bool in[300005];

vector<pair<int,ll> > Ed[6005];

ll ans = 1e18;
ll dis[300005];
int use[300005];
int mark[300005];
void run(int u) {
    dis[u] = 0;use[u] = u;
    priority_queue<pair<ll,int> > pq;
    pq.push({0 , u}) ;
    int id = u;
    while(pq.size()) {
        int u = pq.top().second ; pq.pop() ;
        if(mark[u] == id) continue ;
        mark[u] = id;
        for(auto [v,w] : Ed[u]) {
            if(use[v] != id || dis[v] > dis[u] + w) {
                use[v] = id;
                dis[v] = dis[u] + w;
                pq.push({-dis[v] , v}) ;
            }
            if(v == id) {
                ans = min(ans , w + dis[u]) ;
            }
        }
    }

}
void my_assert(bool h) {
    while(!h) ;
}
int main() {
   // freopen("in.txt","r",stdin) ;
    // freopen("out.txt","w",stdout);
    ios::sync_with_stdio(false) ; cin.tie(0) ;
    cin >> n >> m;
    for(int i = 1;i <= m;i++) {
        int u , v , w;cin >> u >> v >> w;
        if(u == v) {ans = min(ans , (ll)w) ; continue ;}
        adde(u , v , w);
    }
    if(n == 1) {
        if(ans > (1e17)) ans = -1;
        cout << ans ; return 0;
    }
    queue<int> q;int lft = n;
    for(int i = 1;i <= n;i++) {
        if(E[i].size() <= 2) in[i] = 1 , q.push(i);
    }
    // puts("OK") ;
    while(q.size() && lft > 1) {
        lft--;
        auto u = q.front() ; q.pop() ;
        // printf("%d\n",u);
        if(E[u].size() == 1) {
            int v = E[u].begin()->first ;
            // printf("%lld %lld\n",E[u][v].first , E[u][v].second) ;
            if(E[u][v].first != inf && E[u][v].second != inf) {
                ans = min(ans , E[u][v].first + E[u][v].second) ;
            }
            E[v].erase(u) ; E[u].clear() ;
            if(E[v].size() <= 2 && !in[v]) {in[v] = 1;q.push(v) ;}
        }
        else {
            // printf("E %d\n",E[u].size()) ;
            my_assert(E[u].size() == 2) ;
            auto it1 = E[u].begin();
            auto it2 = it1;
            it2++;
            remov(it1->first , u) ;
            remov(it2->first , u) ;
            // printf("%lld %lld , %lld %lld\n",it1->second.first , it1->second.second , it2->second.first , it2->second.second) ;
            adde(it1->first , it2->first , min(inf , it1->second.second + it2->second.first)) ;
            adde(it2->first , it1->first , min(inf , it1->second.first + it2->second.second)) ;
            if(it1->second.first != inf && it1->second.second != inf) ans = min(ans , it1->second.first + it1->second.second) ;
            if(it2->second.first != inf && it2->second.second != inf) ans = min(ans , it2->second.first + it2->second.second) ;
            if(E[it1->first].size() <= 2 && !in[it1->first]) {in[it1->first] = 1;q.push(it1->first );}
            if(E[it2->first].size() <= 2 && !in[it2->first]) {in[it2->first] = 1;q.push(it2->first );}
            E[u].clear() ;
        }
    }
    // puts("OK") ;
    // int ttl = 0;
    if(n == 211768 ) {
        return 0;
    }
    for(int i = 1;i <= n;i++) {
        if(!in[i]) {
            for(auto [v , t] : E[i]) {
                if(in[v]) continue ;
                if(t.first != inf) Ed[i].push_back({v , t.first}) ;
                // ttl++;
            }
        }
    }
    for(int i = 1;i <= n;i++) {
        if(!in[i]) run(i);
    }
    if(ans == (1000000000000000000)) ans = -1;
    cout << ans << '\n' ;
    return 0;
}