#include <bits/stdc++.h>

using i64 = long long;
constexpr int N = 600005;

int n, m, tot;
int u[N << 1], v[N << 1];
i64 w[N << 1];
bool del[N << 1];
std::unordered_set<int> eS[N]; 

inline void add_e(int uu, int vv, i64 ww) {
	++tot;
	u[tot] = uu;
	v[tot] = vv;
	w[tot] = ww;
	eS[uu].insert(tot);
	eS[vv].insert(tot);
}

std::vector<std::pair<int, i64> > g[N];
std::unordered_map<int, i64> dis[N];

std::unordered_set<int> vis;

inline void dij(int s) {
	dis[s][s] = 0;
	vis.clear();
	std::priority_queue <std::pair<i64, int>, std::vector<std::pair<i64, int> >, std::greater<std::pair<i64, int> > > pq;
	pq.emplace(0, s);
	while (!pq.empty()) {
		int u = pq.top().second;
		pq.pop();
		if (vis.count(u)) continue;
		vis.insert(u);
		for (const auto &[v, w] : g[u]) {
			if (!dis[s].count(v) || dis[s][v] > dis[s][u] + w) {
				dis[s][v] = dis[s][u] + w;
				pq.emplace(dis[s][v], v);
			}
		}
	}
}

i64 ans = 0x7fffffffffffffffll;

int main() {
	std::cin >> n >> m;
	for (int i = 1, u, v, w; i <= m; i++) {
		std::cin >> u >> v >> w;
		add_e(u, v, w);
		if (u == v) ans = std::min(ans, 1ll * w);
	}

	auto del_e = [&](int id) {
		eS[u[id]].erase(id);
		eS[v[id]].erase(id);
		del[id] = 1;
	};

	std::queue<int> q;
	auto chk = [&](int u) {
		if (!eS[u].empty() && eS[u].size() <= 2) q.push(u);
	};

	for (int i = 1; i <= n; i++) chk(i);

	while (!q.empty()) {
		int x = q.front();
		q.pop();
		if (eS[x].empty()) continue;
		if (eS[x].size() == 1) {
			int e = *eS[x].begin();
			del_e(e);
			chk(u[e]);
			chk(v[e]);
		}
		else {
			int e1 = *eS[x].begin(), e2 = *std::next(eS[x].begin()); 
			del_e(e1);
			del_e(e2);
			if (v[e2] == u[e1]) std::swap(e1, e2);
			if (v[e1] == u[e2]) {
				add_e(u[e1], v[e2], w[e1] + w[e2]);
				chk(u[e1]);
				chk(v[e2]);
			} else if (u[e1] == u[e2]){
				chk(v[e1]);
				chk(v[e2]);
			} else {
				chk(u[e1]);
				chk(u[e2]);
			}
		}
	}
	if (n >= 20000) return 0;
	for (int i = 1; i <= tot; i++) 
		if (!del[i]) g[u[i]].emplace_back(v[i], w[i]);// std::cout << "ADD: " << u[i] << ' ' << v[i] << ' ' << w[i] << '\n';
	for (int i = 1; i <= n; i++) dij(i);
	for (int u = 1; u <= n; u++) 
		for (const auto &[v, w] : dis[u]) {
			if (v != u && dis[v].count(u)) ans = std::min(ans, dis[v][u] + w);
			// std::cout << u << ' ' << v << ' ' << w << '\n';
		}
	std::cout << (ans == 0x7fffffffffffffffll ? -1 : ans) << '\n';
}