#include <bits/stdc++.h>
using namespace std;

bool Memory_begin;

/*
 */

template <int mod>
unsigned int down(unsigned int x)
{
    return x >= mod ? x - mod : x;
}
template <int mod>
struct Modint
{
    unsigned int x;
    Modint() = default;
    Modint(unsigned int x) : x(x) {}
    friend istream &operator>>(istream &in, Modint &a) { return in >> a.x; }
    friend ostream &operator<<(ostream &out, Modint a) { return out << a.x; }
    friend Modint operator+(Modint a, Modint b) { return down<mod>(a.x + b.x); }
    friend Modint operator-(Modint a, Modint b) { return down<mod>(a.x - b.x + mod); }
    friend Modint operator*(Modint a, Modint b) { return 1ULL * a.x * b.x % mod; }
    friend Modint operator/(Modint a, Modint b) { return a * ~b; }
    friend Modint operator^(Modint a, int b)
    {
        Modint ans = 1;
        for (; b; b >>= 1, a *= a)
            if (b & 1)
                ans *= a;
        return ans;
    }
    friend Modint operator~(Modint a) { return a ^ (mod - 2); }
    friend Modint operator-(Modint a) { return down<mod>(mod - a.x); }
    friend Modint &operator+=(Modint &a, Modint b) { return a = a + b; }
    friend Modint &operator-=(Modint &a, Modint b) { return a = a - b; }
    friend Modint &operator*=(Modint &a, Modint b) { return a = a * b; }
    friend Modint &operator/=(Modint &a, Modint b) { return a = a / b; }
    friend Modint &operator^=(Modint &a, int b) { return a = a ^ b; }
    friend Modint &operator++(Modint &a) { return a += 1; }
    friend Modint operator++(Modint &a, int)
    {
        Modint x = a;
        a += 1;
        return x;
    }
    friend Modint &operator--(Modint &a) { return a -= 1; }
    friend Modint operator--(Modint &a, int)
    {
        Modint x = a;
        a -= 1;
        return x;
    }
    friend bool operator==(Modint a, Modint b) { return a.x == b.x; }
    friend bool operator!=(Modint a, Modint b) { return !(a == b); }
};
const int mod = 1e9 + 7;
typedef Modint<mod> mint;

bool Memory_end;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cerr << (&Memory_end - &Memory_begin) / 1048576.0 << "MB" << '\n';

    int n, m;
    cin >> n >> m;
    vector<int> deg(n + 1), del(n + 1);
    vector<set<pair<int, long long>>> adj(n + 1);
    auto rev = adj;
    for (int i = 1, u, v, w; i <= m; i++)
    {
        cin >> u >> v >> w;
        adj[u].insert({v, w});
        rev[v].insert({u, w});
        deg[u]++, deg[v]++;
    }

    for (int cur = 1; cur <= n; cur++)
    {
        if (deg[cur] != 2)
            continue;
        if (adj[cur].size() == 2 or rev[cur].size() == 2)
        {
            del[cur] = 1;
            adj[cur] = rev[cur] = {};
            deg[cur] = 0;
            continue;
        }
        long long len = adj[cur].begin()->second + rev[cur].begin()->second;
        int to = adj[cur].begin()->first, from = rev[cur].begin()->first;
        deg[cur] = 0;
        adj[from].erase({cur, rev[cur].begin()->second});
        rev[to].erase({cur, adj[cur].begin()->second});
        adj[from].insert({to, len});
        adj[cur] = rev[cur] = {};
        del[cur] = 1;
    }

    long long ans = 1e18;
    for (int t = 1; t <= n; t++)
    {
        vector<pair<int, long long>> tmp{adj[t].begin(), adj[t].end()};
        for (auto &[s, len] : tmp)
        {
            adj[t].erase({s, len});
            vector<long long> dis(n + 1, 1e18);
            vector<int> vis(n + 1);
            dis[s] = 0;
            priority_queue<pair<int, long long>> que;
            que.push({0, s});
            while (!que.empty())
            {
                int cur = que.top().second;
                que.pop();
                if (vis[cur])
                    continue;
                vis[cur] = 1;
                for (auto &[i, w] : adj[cur])
                    if (dis[i] > dis[cur] + w)
                        dis[i] = dis[cur] + w, que.push({-dis[i], i});
            }
            if (dis[t] <= 1e16)
                ans = min(ans, dis[t] + len);
            adj[t].insert({s, len});
        }
    }
    if (ans == 1e18)
        ans = -1;
    cout << ans << '\n';
}
/*
 */