#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int, int> pi;
typedef pair<LL, LL> pl;
typedef __int128_t LLL;
#define fi first
#define lb lower_bound
#define se second
#define V vector
#define pb push_back
#define all0(x) (x).begin(), (x).end()
#define all1(x) (x).begin() + 1, (x).end()
const int INF = 2e9 + 100;

const int MN = 3e5 + 100;

V<pl> e[MN];
LLL dep[MN], rdep[MN];
int f[MN], sz[MN], hs[MN], top[MN];
int l[MN], r[MN], id[MN], tot;
void dfs1(int x, LL w, int p) {
    dep[x] = dep[p] + w, f[x] = p, sz[x] = 1, hs[x] = -1;
    for(auto [y, w] : e[x]) {
        if(y == p) {
            rdep[x] = rdep[y] + w;
            continue;
        }
        dfs1(y, w, x);
        sz[x] += sz[y];
        if(hs[x] == -1 || sz[y] > sz[hs[x]]) hs[x] = y;
    }
}
void dfs2(int x, int t) {
    top[x] = t, l[x] = ++tot, id[l[x]] = x;
    if(hs[x] != -1) {
        dfs2(hs[x], t);
    }
    for(auto [y, w] : e[x]) {
        if(y == f[x] || y == hs[x]) continue;
        dfs2(y, y);
    }
    r[x] = tot;
}
void ini_hdl(int rt) {
    tot = 0;
    dfs1(rt, 1, 0), dfs2(rt, rt);
}
int LCA(int a, int b) {
    while(top[a] != top[b]) {
        if(dep[top[a]] > dep[top[b]]) a = f[top[a]];
        else b = f[top[b]];
    }
    return (dep[a] > dep[b] ? b : a);
}
bool cmp(int x, int y) {
    return l[x] < l[y];
}
V<V<pl>> ve;
V<int> vid;

LL my_abs(LLL x) {
    if(x < 0) x = -x;
    return min((LLL)1e18, x);
}

int u(int x) {
    return lb(all1(vid), x, cmp) - vid.begin();
}

int build(const V<int>& cur) {
    vid = cur;
    sort(all1(vid), cmp);
    for(int i = 1; i < (int)cur.size() - 1; i++) vid.pb(LCA(vid[i], vid[i + 1]));
    sort(all1(vid), cmp);
    vid.erase(unique(all1(vid)), vid.end());
    tot = (int)vid.size() - 1;
    ve.assign(tot + 1, V<pl>());
    for(int i = 1; i < tot; i++) {
        int p = LCA(vid[i], vid[i + 1]);
        int son = vid[i + 1];
        if(my_abs(dep[son] - dep[p]) != 1e18) {
            ve[u(p)].pb({i + 1, my_abs(dep[son] - dep[p])});
        } else {
            ve[u(son)].pb({u(p), my_abs(rdep[son] - rdep[p])});
        }
    }
    return tot;
}

int dsu_f[MN], siz[MN];
int par(int x) {
    if(x == dsu_f[x]) return x;
    return dsu_f[x] = par(dsu_f[x]);
}
void mer(int a, int b) {
    a = par(a), b = par(b);
    if(a == b) return;
    dsu_f[a] = b;
    siz[b] += siz[a];
}
void ini_dsu(int n) {
    for(int i = 1; i <= n; i++) dsu_f[i] = i, siz[i] = 1;
}


void solve() {
    int n, m; cin >> n >> m;
    ini_dsu(n);

    V<array<int, 3>> extra;
    for(int i = 1; i <= m; i++) {
        int a, b, c; cin >> a >> b >> c;
        if(par(a) != par(b)) {
            e[a].pb({b, c});
            e[b].pb({a, (LL)1e18});
            mer(a, b);
        } else {
            extra.pb({a, b, c});
        }
    }

    ini_hdl(1);

    V<int> key_point(1);
    for(auto [x, y, c] : extra) {
        key_point.pb(x);
        key_point.pb(y);
    }
    sort(all1(key_point));
    key_point.erase(unique(all1(key_point)), key_point.end());

    int tot = build(key_point);

    for(auto [x, y, c] : extra) {
        ve[u(x)].pb({u(y), c});
    }

    priority_queue<pl, V<pl>, greater<pl>> pq;
    V<LL> dis(tot + 1, -1);

    LL ans = 1e18;

    for(int x = 1; x <= tot; x++) {
        dis.assign(tot + 1, -1);
        for(auto [y, w] : ve[x]) {
            pq.push({w, y});
        }
        while(pq.size()) {
            auto [w, x] = pq.top();
            pq.pop();
            if(w >= 1e18) continue;
            if(dis[x] != -1) continue;
            dis[x] = w;
            for(auto [y, w] : ve[x]) {
                if(dis[y] != -1) continue;
                pq.push({dis[x] + w, y});
            }
        }
        if(dis[x] != -1) ans = min(ans, dis[x]);
    }

    if(ans >= 1e17) {
        cout << -1 << endl;
    } else cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--) solve();
}