#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <map>

using namespace std;

int read() {
    int x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while('0' <= c && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}

#define Maxn 100005
#define Maxm 100005
#define ULL unsigned long long
#define LL long long
#define L 300
#define MP(x, y) make_pair(x, y)
#define pii pair < LL, int >

struct Edge {
    int next, to, dis;
}
edge[Maxm * 2];
int head[Maxn], deg[Maxn], edge_num;
int n, m, U[Maxm], V[Maxm], D[Maxm];
int bigVer[Maxn], bigCnt; bool isBig[Maxn];

void add_edge(int from, int to, int dis) {
    edge[++edge_num].next = head[from];
    edge[edge_num].to = to;
    edge[edge_num].dis = dis;
    head[from] = edge_num;
}

map < pii, int > ind;
vector < pii > tri[Maxn];
int cmp(pii x, pii y) {
    return x.second > y.second;
}

void addCir(int u, int v, int w) {
    if(u > v) swap(u, v); if(v > w) swap(v, w); if(u > v) swap(u, v); // u < v < w
    int sum = D[ind[MP(u, v)]] + D[ind[MP(v, w)]] + D[ind[MP(w, u)]];
    tri[u].push_back(MP(v * 1e5 + w, sum));
    tri[v].push_back(MP(u * 1e5 + w, sum));
    tri[w].push_back(MP(u * 1e5 + v, sum));
}
bool noRepeat(pii e1, pii e2) {
    int u1 = e1.first / 100000, v1 = e1.first % 100000;
    int u2 = e2.first / 100000, v2 = e2.first % 100000;
    int cnt = 0;
    cnt = (u1 == u2) + (u1 == v2) + (v1 == u2) + (v1 == v2);
    if(cnt) return 0;
    else return 1;
}

void find() {
    for(int i = 1; i <= m; ++i) {
        for(int j = 1; j <= bigCnt; ++j) {
            int w = bigVer[j];
            if(w == U[i] || w == V[i]) continue;
            if(isBig[U[i]] && U[i] > w) continue;
            if(isBig[V[i]] && V[i] > w) continue;
            if(ind.find(MP(U[i], w)) != ind.end() && ind.find(MP(V[i], w)) != ind.end()) addCir(U[i], V[i], w);
        }
    }
    for(int i = 1; i <= m; ++i) {
        if(!isBig[U[i]] && !isBig[V[i]]) {
            for(int e = head[U[i]]; e; e = edge[e].next) {
                int w = edge[e].to;
                if(w <= U[i] || w <= V[i] || isBig[w]) continue;
                if(ind.find(MP(V[i], w)) != ind.end()) addCir(U[i], V[i], w);
            }
        }
    }
}

int main() {
    n = read(); m = read();
    for(int i = 1; i <= m; ++i) {
        U[i] = read(); V[i] = read(); D[i] = read();
        add_edge(U[i], V[i], D[i]); add_edge(V[i], U[i], D[i]);
        ind[make_pair(U[i], V[i])] = ind[make_pair(V[i], U[i])] = i;
        ++deg[U[i]]; ++deg[V[i]];
    }
    for(int i = 1; i <= n; ++i) {
        if(deg[i] >= L) bigVer[++bigCnt] = i, isBig[i] = 1;
    }

    find();
    
    int ans = -1;
    for(int x = 1; x <= n; ++x) { // Fix a vertex first
        sort(tri[x].begin(), tri[x].end(), cmp);
        for(int i = 0; i < min((int)(tri[x].size()), 16); ++i) {
            for(int j = i + 1; j < tri[x].size(); ++j) {
                pii e1 = tri[x][i], e2 = tri[x][j];
                if(noRepeat(e1, e2)) {
                    int sum = e1.second + e2.second;
                    if(sum <= ans) break;
                    else ans = sum;
                }
            }
        }
    }
    
    cout << ans << endl;
    return 0;
}