#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#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 L 320
#define MP(x, y) make_pair(x, y)

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];
map < pair <int, int> , int> ind;

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;
}

int ban[Maxm];
bool check(int u, int v) {
    if(ind.find(MP(u, v)) == ind.end()) return 0;
    if(ban[ind[MP(u, v)]]) return 0;
    return 1;
}

int buf[20], tot;
void find() {
    int rec1, rec2, rec3, sum = 0;
    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(check(U[i], w) && check(V[i], w) && check(U[i], V[i])) {
                int cur = D[i] + D[ind[MP(U[i], w)]] + D[ind[MP(V[i], w)]];
                if(cur > sum) {
                    sum = cur;
                    rec1 = w, rec2 = U[i], rec3 = V[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 == V[i]) continue;
                if(check(U[i], w) && check(V[i], w) && check(U[i], V[i])) {
                    int cur = D[i] + edge[e].dis + D[ind[MP(V[i], w)]];
                    if(cur > sum) {
                        sum = cur;
                        rec1 = w, rec2 = U[i], rec3 = V[i];
                    }
                } 
            }
        }
    }
    buf[++tot] = rec1; buf[++tot] = rec2; buf[++tot] = rec3; buf[++tot] = sum;
    // cout << rec1 << " " << rec2 << " " << rec3 << " " << sum << endl;
}

int sum1[2], sum2[2], sum3[2], rec1[2], rec2[2], rec3[2];
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;
    }

    int ans = -1, ans0 = -1;

    // Find 1
    find();
    ban[ind[MP(buf[1], buf[2])]] = ban[ind[MP(buf[2], buf[3])]] = ban[ind[MP(buf[3], buf[1])]] = 1;

    // Find 2
    find();
    if(buf[1] == buf[5] || buf[1] == buf[6] || buf[1] == buf[7] ||
       buf[2] == buf[5] || buf[2] == buf[6] || buf[2] == buf[7] ||
       buf[3] == buf[5] || buf[3] == buf[6] || buf[3] == buf[7] ) {
        ans0 = buf[4] + buf[8];
    }
    ban[ind[MP(buf[1], buf[2])]] = ban[ind[MP(buf[2], buf[3])]] = ban[ind[MP(buf[3], buf[1])]] = 0;
    for(int i = 1; i <= n; ++i) {
        if(i == buf[1] || i == buf[2] || i == buf[3]) continue;
        if(check(i, buf[1]) && check(i, buf[2])) {
            int cur = D[ind[MP(i, buf[1])]] + D[ind[MP(i, buf[2])]] + D[ind[MP(buf[1], buf[2])]];
            if(cur >= sum1[0]) {
                sum1[1] = sum1[0], rec1[1] = rec1[0];
                sum1[0] = cur, rec1[0] = i;
            }
            else if(cur > sum1[1]) {
                sum1[1] = cur, rec1[1] = i;
            }
        }
    }
    for(int i = 1; i <= n; ++i) {
        if(i == buf[1] || i == buf[2] || i == buf[3]) continue;
        if(check(i, buf[2]) && check(i, buf[3])) {
            int cur = D[ind[MP(i, buf[2])]] + D[ind[MP(i, buf[3])]] + D[ind[MP(buf[2], buf[3])]];
            if(cur >= sum2[0]) {
                sum2[1] = sum2[0], rec2[1] = rec2[0];
                sum2[0] = cur, rec2[0] = i;
            }
            else if(cur > sum2[1]) {
                sum2[1] = cur, rec2[1] = i;
            }
        }
    }
    for(int i = 1; i <= n; ++i) {
        if(i == buf[1] || i == buf[2] || i == buf[3]) continue;
        if(check(i, buf[3]) && check(i, buf[1])) {
            int cur = D[ind[MP(i, buf[3])]] + D[ind[MP(i, buf[1])]] + D[ind[MP(buf[3], buf[1])]];
            if(cur >= sum3[0]) {
                sum3[1] = sum3[0], rec3[1] = rec3[0];
                sum3[0] = cur, rec3[0] = i;
            }
            else if(cur > sum3[1]) {
                sum3[1] = cur, rec3[1] = i;
            }
        }
    }
    if(rec1[0] == rec2[0] && rec2[0] == rec3[0]) {
        ans = max(max(sum1[0], sum2[0]), sum3[0]) + max(max(sum1[1], sum2[1]), sum3[1]);
    }
    else if(rec1[0] == rec2[0]) ans = sum1[0] + sum3[0];
    else if(rec1[0] == rec3[0]) ans = sum1[0] + sum2[0];
    else if(rec2[0] == rec3[0]) ans = sum1[0] + sum2[0];
    else {
        int a[4] = {0, sum1[0], sum2[0], sum3[0]};
        sort(a + 1, a + 4);
        ans = a[3] + a[2];
    }
    ans = max(ans, ans0);
    cout << ans << endl;
    return 0;
}