#include <ctime>
#include <iostream>
#include <cassert>
#include <queue>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <bitset>
using namespace std;
#define int long long
#define debug puts("qwq")
#define open(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define close fclose(stdin);fclose(stdout);
#define all(x) x.begin(), x.end()
namespace FastIO {
	template <typename T = int>
	inline T read() {
		T s = 0, w = 1;
		char c = getchar();
		while (!isdigit(c)) {
			if (c == '-') w = -1;
			c = getchar();
		}
		while (isdigit(c)) s = (s << 1) + (s << 3) + (c ^ 48), c = getchar();
		return s * w;
	}
	template <typename T>
	inline void read(T &s) {
		s = 0;
		int w = 1;
		char c = getchar();
		while (!isdigit(c)) {
			if (c == '-') w = -1;
			c = getchar();
		}
		while (isdigit(c)) s = (s << 1) + (s << 3) + (c ^ 48), c = getchar();
		s = s * w;
	}
	template <typename T, typename... Args> inline void read(T &x, Args &...args) {
		read(x), read(args...);
	}
	template <typename T>
	inline void write(T x, char ch) {
		if (x < 0) x = -x, putchar('-');
		static char stk[25];
		int top = 0;
		do {
			stk[top++] = x % 10 + '0', x /= 10;
		} while (x);
		while (top) putchar(stk[--top]);
		putchar(ch);
		return;
	}
} using namespace FastIO;
const int N=4e5+19;
#define pii pair<int, int>
int ans=1e18, head[N], nxt[N], edge[N], cnt, val[N], n, m, in[N], out[N], X[N], Y[N], Z[N], Q[N], del[N], vis[N], QwQ, dis[N];
vector<pii> g[N]; vector<int> alive;
void addedge(int x, int y, int z) {
	edge[++cnt]=y;
	nxt[cnt]=head[x];
	val[cnt]=z;
	head[x]=cnt;
	out[x]++; in[y]++;
}
int hd[N], nx[N], ed[N], CNT, va[N];
void ae(int x, int y, int z) {
	ed[++CNT]=y;
	nx[CNT]=hd[x];
	va[CNT]=z;
	hd[x]=CNT;
}
void topsort() {
	int H=1,T=0;
	for (int i=1;i<=n;++i) if (!in[i]) Q[++T]=i,del[i]=1;
	while (H<=T) {
		int u=Q[H++];
		for (int i=head[u];i;i=nxt[i]) {
			out[u]--;
			if(!--in[edge[i]]) {
				Q[++T]=edge[i];
				del[edge[i]]=1;
			}
		}
	}
}
void Topsort() {
	int H=1,T=0;
	for (int i=1;i<=n;++i) if (!out[i]) Q[++T]=i;
	while (H<=T) {
		int u=Q[H++];
		for (int i=hd[u];i;i=nx[i]) {
			in[u]--;
			if (!--out[ed[i]]) {
				del[ed[i]]=1;
				Q[++T]=ed[i];
			}
		}
	}
}
int get_from(int u) {
	if (out[u]==1) {
		if (in[u]==1) {
			del[u]=1;
			in[u]--; out[u]--;
			QwQ+=va[hd[u]];
			return get_from(ed[hd[u]]);
		}
	}
	out[u]--;
	return u;
}
int get_to(int u) {
	if (in[u]==1) {
		if (out[u]==1) {
			in[u]--; out[u]--;
			del[u]=1;
			QwQ+=val[head[u]];
			return get_to(edge[head[u]]);
		}
	}
	in[u]--;
	return u;
}
signed main() {
	read(n, m);
	for (int i=1;i<=m;++i) {
		read(X[i],Y[i],Z[i]);
		if (X[i]==Y[i]) {
			ans=min(ans,Z[i]);
			continue;
		}
		addedge(X[i],Y[i],Z[i]);
		ae(Y[i],X[i],Z[i]);
	}
	topsort();Topsort();
	for (int i=1;i<=n;++i) hd[i]=head[i]=in[i]=out[i]=0;
	CNT=cnt=0;
	for (int i=1;i<=m;++i) {
		if (X[i]^Y[i] && !del[X[i]] && !del[Y[i]]) addedge(X[i],Y[i],Z[i]),ae(Y[i], X[i], Z[i]);
	}
	for (int i=1;i<=n;++i) {
		if (in[i]==1&&out[i]==1) {
			del[i]=1;
			QwQ=va[hd[i]];
			in[i]--;
			int fr=get_from(ed[hd[i]]);
			if (fr==i) {
				ans=min(ans,QwQ);
				continue;
			}
			QwQ+=val[head[i]];
			out[i]--;
			int ot=get_to(edge[head[i]]);
			if (fr==ot) {
				ans=min(ans,QwQ);
				continue;
			}
			in[ot]++; out[fr]++;
			g[fr].emplace_back(make_pair(ot,QwQ));
		}
	}
	for (int i=1;i<=n;++i) if (!del[i]) alive.push_back(i);
	for (int i=1;i<=m;++i) {
		if (X[i]^Y[i] &&!del[X[i]]&&!del[Y[i]]) g[X[i]].emplace_back(make_pair(Y[i], Z[i]));
	}
	for (int i=1;i<=n;++i) {
		if (del[i]) continue;
		for (int j:alive) vis[j]=0,dis[j]=1e18;
		dis[i]=0;
		priority_queue<pii, vector<pii>, greater<pii> > q;
		q.push({0,i});
		while (!q.empty()) {
			auto u=q.top();
			q.pop();
			if (vis[u.second]) continue;
			vis[u.second]=1;
			for (auto [i,j]:g[u.second]) {
				if (dis[i]>u.first+j) {
					dis[i]=u.first+j;
					q.push({dis[i],i});
				}
			}
		}
		for (int x:alive) {
			for (auto [_1,_2]:g[x]) if (_1==i) {ans=min(ans,dis[x]+_2); if(dis[x] + _2 == 98674714245) (std::cout << x << ' ' << i << '\n');
		}
	}
	write(ans==1e18?-1:ans,'\n');
	return 0;
}

answer.code: In function ‘int main()’:
answer.code:178:35: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  178 |                         for (auto [i,j]:g[u.second]) {
      |                                   ^
answer.code:186:35: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  186 |                         for (auto [_1,_2]:g[x]) if (_1==i) {ans=min(ans,dis[x]+_2); if(dis[x] + _2 == 98674714245) (std::cout << x << ' ' << i << '\n');
      |                                   ^
answer.code:191:2: error: expected ‘}’ at end of input
  191 | }
      |  ^
answer.code:125:15: note: to match this ‘{’
  125 | signed main() {
      |               ^