#include <bits/stdc++.h>
#define _rep(i, x, y) for(int i = x; i <= y; ++i)
#define _req(i, x, y) for(int i = x; i >= y; --i)
#define _rev(i, u) for(int i = head[u]; i; i = e[i].nxt)
#define pb push_back
#define fi first
#define se second
#define mst(f, i) memset(f, i, sizeof f)
using namespace std;
#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif
typedef long long ll;
typedef pair<ll, ll> PII;
namespace fastio{
    #ifdef ONLINE_JUDGE
    char ibuf[1 << 20],*p1 = ibuf, *p2 = ibuf;
    #define get() p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++
    #else
    #define get() getchar()
    #endif
    template<typename T> inline void read(T &t){
        T x = 0, f = 1;
        char c = getchar();
        while(!isdigit(c)){
            if(c == '-') f = -f;
            c = getchar();
        }
        while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
        t = x * f;
    }
    template<typename T, typename ... Args> inline void read(T &t, Args&... args){
        read(t);
        read(args...);
    }
    template<typename T> void write(T t){
        if(t < 0) putchar('-'), t = -t;
        if(t >= 10) write(t / 10);
        putchar(t % 10 + '0');
    }
    template<typename T, typename ... Args> void write(T t, Args... args){
        write(t), putchar(' '), write(args...);
    }
    template<typename T> void writeln(T t){
        write(t);
        puts("");
    }
    template<typename T> void writes(T t){
        write(t), putchar(' ');
    }
    #undef get
};
using namespace fastio;
#define multitest() int T; read(T); _rep(tCase, 1, T)
namespace Calculation{
    const ll mod = 998244353;
    ll ksm(ll p, ll h){ll base = p % mod, res = 1; while(h){if(h & 1ll) res = res * base % mod; base = base * base % mod, h >>= 1ll;} return res;}
    void dec(ll &x, ll y){x = ((x - y) % mod + mod) % mod;}
    void add(ll &x, ll y){x = (x + y) % mod;}
    void mul(ll &x, ll y){x = x * y % mod;}
    ll sub(ll x, ll y){return ((x - y) % mod + mod) % mod;}
    ll pls(ll x, ll y){return ((x + y) % mod + mod) % mod;}
    ll mult(ll x, ll y){return x * y % mod;}
}
using namespace Calculation;
const int N = 4e5 + 5, M = 3005;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n, m;
vector<PII> G[N], g[N];
struct edge{
    int u, v, w;
}e[N];
int cnt, id[N];
int dep[N], pre[N], w[N];
ll dis[N];
bool flag[N];
int tt = 0;
void dfs(int u, int fa){
    dep[u] = dep[fa] + 1, pre[u] = fa;
    tt++;
    for(auto &[v, i] : G[u]){
        if(dep[v]){
            if(n > 2323) printf("fff\n");
            flag[i] = 1;
            continue;
        }
        g[u].pb({v, i});
        // debug("u:%d v:%d i:%d\n", u, v, i);
        w[v] = e[i].u == u, dis[v] = dis[u] + e[i].w;
        dfs(v, u);
    }
}
vector<int> dfs2(int u){
    vector<int> cur;
    for(auto &[v, i] : g[u]){
        vector<int> t = dfs2(v);
        if(w[v] == w[u]) for(auto &j : t) cur.pb(j);
        if(id[u]){
            for(auto &j : t){
                if(w[v]) G[id[u]].pb({id[j], dis[j] - dis[u]});
                else G[id[j]].pb({id[u], dis[j] - dis[u]});
            }
        }
    }
    if(id[u]) cur.pb(u);
    return cur;
}
ll d[M], nxt[M][M];
bool vis[N];
ll dij(int s, ll *dis){
    _rep(i, 1, cnt) dis[i] = inf, vis[i] = 0;
    priority_queue<PII, vector<PII>, greater<PII> > q;
    q.push({dis[s] = 0, s});
    while(q.size()){
        int u = q.top().se; q.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        for(auto &[v, w] : G[u]){
            if(dis[v] > dis[u] + w){
                dis[v] = dis[u] + w;
                q.push({dis[v], v});
            }
        }
    }
    ll res = inf;
    _rep(i, 1, n) if(nxt[i][s] != inf) res = min(res, dis[i] + nxt[i][s]);
    return res;
}
int main(){
    read(n, m);
    _rep(i, 1, m){
        int u, v, w; read(u, v, w);
        e[i] = {u, v, w};
        G[u].pb({v, i}), G[v].pb({u, i});
    }
    dfs(1, 0);
    if(n > 2323) return writeln(tt), 0;
    _rep(i, 1, n) G[i].clear();
    _rep(i, 1, m){
        if(!flag[i]) continue;
        if(!id[e[i].u]) id[e[i].u] = ++cnt;
        if(!id[e[i].v]) id[e[i].v] = ++cnt;
        // debug("%d -> %d\n", id[e[i].u], id[e[i].v]);
        G[id[e[i].u]].pb({id[e[i].v], e[i].w});
    }
    assert(cnt <= 1500);
    dfs2(1);
    _rep(i, 1, cnt) _rep(j, 1, cnt) nxt[i][j] = inf;
    _rep(i, 1, cnt) for(auto &[j, w] : G[i]) nxt[i][j] = min(nxt[i][j], w);
    ll ans = inf;
    _rep(i, 1, cnt){
        ans = min(ans, dij(i, d));
    }
    writeln(ans == inf ? -1 : ans);
    return 0;
}