#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 = 317;
int n, m, s[N * 2];
unordered_map <int, int> g[N];
void upd(int pos, int val, int max_range) {
	for (s[pos += max_range] = val; pos /= 2;)
		s[pos] = max(s[pos * 2], s[pos * 2 + 1]);
}
int get(int b, int e, int max_range) {
	++e;
	int ra = 0, rb = 0;
	for (b += max_range, e += max_range; b < e; b /= 2, e /= 2) {
		if (b % 2) ra = max(ra, s[b++]);
		if (e % 2) rb = max(s[--e], rb);
	}
	return max(ra, rb);
}
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});
					}
				}
			}
			reverse(all(vec));
			for (int i = 0; i <= sz(nodes) * 2; ++i)
				s[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 = 0;
					if (vec[k].f.s + 1 < vec[k].f.f)
						ret = get(vec[k].f.s + 1, vec[k].f.f - 1, sz(nodes));
					if (vec[k].f.s > 0)
						ret = max(ret, get(0, vec[k].f.s - 1, sz(nodes)));
					if (vec[k].f.f + 1 < sz(nodes))
						ret = max(ret, get(vec[k].f.f + 1, sz(nodes) - 1, sz(nodes)));
					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, vec[k].s, sz(nodes));
				}
				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 - 1, y - 1}, tot});
			}
			sort(all(vec));
			reverse(all(vec));
			for (int i = 0; i <= n * 2; ++i)
				s[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 = 0;
					if (vec[k].f.s + 1 < vec[k].f.f)
						ret = get(vec[k].f.s + 1, vec[k].f.f - 1, n);
					if (vec[k].f.s > 0)
						ret = max(ret, get(0, vec[k].f.s - 1, n));
					if (vec[k].f.f + 1 < n)
						ret = max(ret, get(vec[k].f.f + 1, n - 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, vec[k].s, n);
				}
				i = j;
			}	
		}
	}
	if (!ans) ans = -1;
	cout << ans;
	return 0;
}