#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], rev[N];
int dep[N], w[N];
ll dis[N];
bool flag[N];
void dfs(int u, int fa, int lst = 0){
    dep[u] = dep[fa] + 1;
    for(auto &[v, i] : G[u]){
        if(dep[v]){
            if(i != lst) flag[i] = 1;
            continue;
        }
        g[u].pb({v, i});
        debug("%d -> %d i:%d\n", u, v, i);
        w[v] = e[i].u == u, dis[v] = dis[u] + e[i].w;
        dfs(v, u, i);
    }
}
int pre[N][25];
PII f[N][25];
PII operator+(PII x, PII y){return make_pair(x.fi + y.fi, (x.se == -1 || y.se == -1 || x.se != y.se) ? -1 : x.se);}
void dfs2(int u){
    _rep(i, 1, 20) f[u][i] = f[u][i - 1] + f[pre[u][i - 1]][i - 1], pre[u][i] = pre[pre[u][i - 1]][i - 1];
    for(auto &[v, i] : g[u]){
        f[v][0] = {e[i].w, w[v]}, pre[v][0] = u;
        dfs2(v);
    }
}
int lca(int x, int y){
    if(dep[x] < dep[y]) swap(x, y);
    int h = dep[x] - dep[y], p = 0;
    // debug("lca(%d,%d) H:%d\n", x, y, h);
    while(h){if(h & 1) x = pre[x][p]; h >>= 1, p++;}
    if(x == y) return x;
    _req(i, 20, 0) if(pre[x][i] != pre[y][i]) x = pre[x][i], y = pre[y][i];
    return pre[x][0];
}
PII jump(int u, int h){
    PII cur = {0, 0};
    _req(i, 20, 0){
        if(h >> i & 1){
            if(!cur.fi) cur = f[u][i];
            else cur = cur + f[u][i];
            u = pre[u][i];
        }
    }
    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, cnt) 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);
    _rep(i, 1, n) G[i].clear();
    _rep(i, 1, m){
        if(!flag[i]) continue;
        if(!id[e[i].u]) rev[id[e[i].u] = ++cnt] = e[i].u;
        if(!id[e[i].v]) rev[id[e[i].v] = ++cnt] = e[i].v;
        G[id[e[i].u]].pb({id[e[i].v], e[i].w});
    }
    dfs2(1);
    _rep(i, 1, cnt){
        _rep(j, 1, cnt){
            if(i == j) continue;
            int x = rev[i], y = rev[j], z = lca(x, y);
            // debug("x:%d y:%d z:%d\n", x, y, z);
            PII L = jump(x, dep[x] - dep[z]), R = jump(y, dep[x] - dep[z]);
            if(L.se == -1 || R.se == -1 || L.se == R.se) continue;
            if(L.se) G[j].pb({i, L.fi + R.fi});
            else G[i].pb({j, L.fi + R.fi});
        }
    }
    _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;
}