#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <list>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER)
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define EPS 1e-9
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll;
typedef vector<string> vs; typedef long double ld;

int n, m;
int indeg[100001], outdeg[100001];
vector<pair<int,ll> > edges[100001];

bool is_super(int i) {
	return i == 0 || i == n-1 || indeg[i] != 1 || outdeg[i] != 1;
}

int root[100001], root2[100001], last[100001]; ll dists[100001], dists2[100001];
vector<pair<int,ll> > superedges[100001];
int superid[100001];
ll superdists[1111][1111];

int dfs(int i, bool first, int a, int b, ll dist, ll &dist2) {
	if(!first && is_super(i)) {
		superedges[a].push_back(mp(i, dist));
		dist2 = 0;
		return i;
	}else {
		root[i] = a;
		root2[i] = first ? i : b;
		dists[i] = dist;
		int l = -INF;
		each(j, edges[i]) {
			l = dfs(j->first, false, a, b == -1 ? j->first : b, dist+j->second, dist2);
		}
		if(first) last[i] = i, dists2[i] = 0;
		else {
			each(j, edges[i]) dist2 += j->second;
			last[i] = l, dists2[i] = dist2;
		}
		return l;
	}
}
struct S {
	int i; ll d;
	S(int i_, ll d_): i(i_), d(d_) {}
};
bool operator<(const S &s, const S &t) {
	return s.d > t.d;
}

ll getdist(int i, int j) {
	if((root2[i] == root2[j] || root[j] == i) && dists[i] <= dists[j])
		return dists[j] - dists[i];
	ll d = superdists[superid[last[i]]][superid[root[j]]];
	if(d == INFL)
		return INFL;
	return d + dists2[i] + dists[j];
}

int main() {
	scanf("%d%d", &n, &m);
	rep(i, m) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		a --, b --;
		edges[a].pb(mp(b, c));
		outdeg[a] ++;
		indeg[b] ++;
	}
	int supers = 0;
	rep(i, n) if(is_super(i)) supers ++;
	if(supers > 1100) {
		cout << "-1" << endl;
		return 0;
	}
	supers = 0;
	rep(i, n) if(is_super(i)) {
		ll d;
		dfs(i, true, i, -1, 0, d);
		superid[i] = supers;
		supers ++;
	}
	mset(superdists, INF);
	rep(i, n) if(is_super(i)) {
		static bool vis[1111];
		mset(vis, 0);
		int id = superid[i];
		priority_queue<S> q;
		q.push(S(i, 0));
		while(!q.empty()) {
			S s = q.top(); q.pop();
			int sid = superid[s.i];
			if(vis[sid]) continue;
			superdists[id][sid] = s.d;
			vis[sid] = 1;
			each(j, superedges[s.i])
				q.push(S(j->first, s.d + j->second));
		}
	}
	ll r = 0;
	rep(i, n) {
		ll d = getdist(i, (i+1)%n);
		if(d == INFL) {
			cout << "-1" << endl;
			return 0;
		}
		r += d;
	}
	cout << r << endl;
	return 0;
}

Measured memory_bytes: 28820