#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define f first
#define s second
using namespace std;
using ll = long long;
using pii = pair <int, int>;
const int N = 1e5 + 3, K = 0;
int n, m, t[N * 4], mx[N * 4];
unordered_map <int, int> g[N];
void push(int v, int tl, int tr) {
	if (mx[v]) {
		t[v] = max(t[v], mx[v]);
		if (tl != tr) {
			mx[v * 2] = max(mx[v * 2], mx[v]);
			mx[v * 2 + 1] = max(mx[v * 2 + 1], mx[v]);
		}
		mx[v] = 0;
	}
}
void upd(int l, int r, int x, int v, int tl, int tr) {
	push(v, tl, tr);
	if (l > r || l > tr || r < tl)
		return;
	if (l <= tl && tr <= r) {
		mx[v] = max(mx[v], x);
		push(v, tl, tr);
		return;
	}
	int tm = (tl + tr) / 2;
	upd(l, r, x, v * 2, tl, tm);
	upd(l, r, x, v * 2 + 1, tm + 1, tr);
	t[v] = max(t[v * 2], t[v * 2 + 1]);
}
int get(int x, int v, int tl, int tr) {
	push(v, tl, tr);
	if (tl == tr)
		return t[v];
	int tm = (tl + tr) / 2;
	if (x <= tm)
		return get(x, v * 2, tl, tm);
	return get(x, v * 2 + 1, tm + 1, tr);
}
int main() {
	ios :: sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	vector <pii> edges;
	for (int i = 1; i <= m; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		edges.pb({u, v});
		g[u][v] = g[v][u] = w;
	}
	// fix a host
	int ans = 0;
	for (int v = 1; v <= n; ++v) {
		if (sz(g[v]) < 4)
			continue;
		if (sz(g[v]) <= K) {
			vector <pii> nodes;
			for (auto x : g[v]) 
				nodes.pb(x);
			sort(all(nodes));
			vector <pair <pii, int> > vec;
			for (int i = 0; i < sz(nodes); ++i) {
				auto [u1, w1] = nodes[i];
				for (int j = 0; j < i; ++j) {
					auto [u2, w2] = nodes[j];
					if (g[u1].count(u2)) {
						int tot = w1 + w2 + g[u1][u2];
						vec.pb({{i, j}, tot});
					}
				}
			}
			for (int i = 1; i <= sz(nodes) * 4; ++i)
				t[i] = mx[i] = 0;
			for (int i = 0; i < sz(vec); ++i) {
				int j = i;
				while (j + 1 < sz(vec) && vec[j + 1].f.f == vec[j].f.f)
					++j;
				for (int k = i; k <= j; ++k) {
					int ret = get(vec[k].f.s, 1, 0, sz(nodes) - 1);
					if (ret > 0)
						ans = max(ans, ret + vec[k].s);
				}
				for (int k = i; k <= j; ++k) {
					auto [y, x] = vec[k].f;
					upd(x + 1, y - 1, vec[k].s, 1, 0, sz(nodes) - 1);
					upd(0, x - 1, vec[k].s, 1, 0, sz(nodes) - 1);
					upd(y + 1, sz(nodes) - 1, vec[k].s, 1, 0, sz(nodes) - 1);
				}
				i = j;
			}
			
		}
		else {
			vector <pair <pii, int> > vec;
			for (auto [x, y] : edges) {
				if (!g[v].count(x) || !g[v].count(y))
					continue;
				if (x < y)
					swap(x, y);
				int tot = g[v][x] + g[v][y] + g[x][y];
				vec.pb({{x, y}, tot});
			}
			
			for (int i = 1; i <= n * 4; ++i)
				t[i] = mx[i] = 0;
			
			for (int i = 0; i < sz(vec); ++i) {
				int j = i;
				while (j + 1 < sz(vec) && vec[j + 1].f.f == vec[j].f.f)
					++j;
				for (int k = i; k <= j; ++k) {
					int ret = get(vec[k].f.s, 1, 1, n);
					if (ret > 0)
						ans = max(ans, ret + vec[k].s);
				}
				for (int k = i; k <= j; ++k) {
					auto [y, x] = vec[k].f;
					upd(x + 1, y - 1, vec[k].s, 1, 1, n);
					upd(1, x - 1, vec[k].s, 1, 1, n);
					upd(y + 1, n, vec[k].s, 1, 1, n);
				}
				i = j;
			}
			
		}
	}
	if (!ans) ans = -1;
	cout << ans;
	return 0;
}