#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int N = 1e5 + 10;
int n, m;
int to[N];
pii val[N];
vector<pii> g[N];
vector<vector<int>> vec[N];
inline void Update(vector<int> &v, vector<int> a) {
    if (a[0] > v[0]) v = a;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, x, y, z; i <= m; ++i) {
        scanf("%d%d%d", &x, &y, &z);
        g[x].push_back(pii(y, z));
        g[y].push_back(pii(x, z));
    }
    for (int i = 1; i <= n; ++i) val[i] = pii(g[i].size(), i);
    for (int i = 1; i <= n; ++i) {
        sort(g[i].begin(), g[i].end(), [](pii u, pii v) {
            int x = u.first, y = v.first;
            return val[x] < val[y];
        });
    }
    for (int i = 1; i <= n; ++i) {
        for (auto [j, dis] : g[i]) if (val[j] < val[i]) {
            to[j] = dis;
        } else break;
        for (auto [j, d1] : g[i]) if (val[j] < val[i]) {
            for (auto [k, d2] : g[j]) if (val[k] < val[j]) {
                if (to[k]) {
                    int len = d1 + d2 + to[k];
                    vec[i].push_back({len, j, k});
                    vec[j].push_back({len, i, k});
                    vec[k].push_back({len, j, i});
                }
            } else break;
        } else break;
        for (auto [j, dis] : g[i]) if (val[j] < val[i]) {
            to[j] = 0;
        } else break;
    }
    int ans = -1;
    for (int x = 1; x <= n; ++x) if (vec[x].size()) {
        vector<int> mx[3];
        mx[0].resize(3, -1e8);
        mx[1].resize(3, -1e8);
        mx[2].resize(3, -1e8);
        mx[0] = *max_element(vec[x].begin(), vec[x].end(), [](vector<int> a, vector<int> b) {
            return a[0] < b[0];
        });
        for (auto v : vec[x]) {
            if (v[1] != mx[0][1] && v[2] != mx[0][1]) Update(mx[1], v);
            if (v[1] != mx[0][2] && v[2] != mx[0][2]) Update(mx[2], v);
        }
        for (auto v : vec[x]) {
            for (int i = 0; i < 3; ++i) {
                // Update(mx[i], v);
                if (v[1] != mx[i][1] && v[1] != mx[i][2] && v[2] != mx[i][1] && v[2] != mx[i][2]) ans = max(ans, v[0] + mx[i][0]);
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}