#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define lowbit(x) ((x) & (-x))
constexpr int N = 2e5 + 10;
constexpr int M = 5e5 + 10;
constexpr ll mod = (1LL<<20);
constexpr int INF = 0x3f3f3f3f;
constexpr ll Base = 131;
constexpr int MAXBIT = 30;

#define pb push_back
constexpr int maxn = 1e6 + 10;
constexpr ll LNF = 0x3f3f3f3f3f3f3f3f;
#define int long long 
ll n, m, ans = LNF;

int top = 0;
pll st[maxn];
bool vis[maxn], inst[maxn];
vector<pll> g[maxn];

void dfs(int u, ll fauw = 0)
{
	vis[u] = 1;
	inst[u] = true;
	st[++ top] = {u, fauw};

	for(auto it : g[u])
	{
		ll v = it.first, w = it.second;
		if(vis[v])
		{
			if(inst[v])
			{
				// vector<int> path;
				// path.pb(v);

				int t = top;
				ll res = w;
				while(st[t].first != v)
				{
					// path.pb(st[t].first);
					res += st[t--].second;
				}
				if(res < ans) ans = res;
				// cout << res << "  -> ";
				// for(auto j : path)
				// 	cout << j << " ";
				// cout << "\n";
			}
			continue;
		}
		dfs(v, w);
	}

	inst[u] = false;
	-- top;
}

void solve()
{   
    cin >> n >> m;
	for(int i = 1; i <= m; i ++)
	{
		ll u, v, w;
		cin >> u >> v >> w;
		g[u].pb({v, w});
	}
	// for(int i = n; i >= 1; i --)
	for(int i = 1; i <= n; i ++)
		if(!vis[i]) {
			dfs(i);
		}
	
	if(n >= 2) 
	{
		memset(vis, 0, sizeof(vis));
		memset(inst, false, sizeof(inst));
		top = 0;

		int flag = n / 4 + 1;
		dfs(flag);

		for(int i = n; i >= 1; i --)
			if(!vis[i]) {
				dfs(i);
			}
	}

	if(ans == LNF) cout << -1 << '\n';
	else cout << ans << "\n";
}
signed main()
{
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    // #ifndef ONLINE_JUDGE
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    // #endif
    int _ = 1;
    // cin >> _;
    while (_--)
        solve();
    return 0;
}