#define _USE_MATH_DEFINES
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int v, w; };

ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;
int INF = INT_MAX / 4;

void dijkstra(int n, vector<vector<edge> >& G, int s, vector<int>& d) {
	d[s] = 0;
	priority_queue<i_i, vector<i_i>, greater<i_i> > q;
	q.push(i_i(0, s));
	while (!q.empty()) {
		i_i p = q.top(); q.pop();
		int u = p.second;
		if (p.first > d[u]) continue;
		for (int i = 0; i < G[u].size(); i++) {
			edge e = G[u][i];
			if (d[e.v] > d[u] + e.w) {
				d[e.v] = d[u] + e.w;
				q.push(i_i(d[e.v], e.v));
			}
		}
	}
}

int unko = 0;

void dfs(int u, vector<vector<edge> >& g, vector<int>& in, vector<bool>& vis, vector<vector<edge> >& G, vector<i_i>& a, vector<i_i>& b, vector<int>& c) {
	if (vis[u]) return;
	vis[u] = true;
	a[u] = b[u] = i_i(u, 0);
	for (int i = 0; i < g[u].size(); i++) {
		edge e = g[u][i];
		edge f;
		int sum = 0;
		for (f = e; in[f.v] == 1 && g[f.v].size() == 1; f = g[f.v][0])
			sum += f.w;
		sum += f.w;
		edge E = {f.v, sum};
		G[u].push_back(E);
		int x = 0;
		for (f = e; in[f.v] == 1 && g[f.v].size() == 1; f = g[f.v][0]) {
			x += f.w;
			a[f.v] = i_i(E.v, sum - x);
			b[f.v] = i_i(u, x);
			c[f.v] = unko;
		}
		unko++;
		dfs(E.v, g, in, vis, G, a, b, c);
	}
}

int main() {
	int N, M;
	cin >> N >> M;
	vector<int> in(N);
	vector<vector<edge> > g(N);
	in[0]++;
	edge e = {0, 0};
	g[0].push_back(e);
	while (M--) {
		int a, b, c;
		cin >> a >> b >> c;
		a--; b--;
		in[b]++;
		edge e = {b, c};
		g[a].push_back(e);
	}
	for (int u = 0; u < N; u++)
		if (in[u] == 0 || g[u].empty()) {
			cout << -1 << endl;
			return 0;
		}
	vector<bool> vis(N);
	vector<vector<edge> > G(N);
	vector<i_i> a(N), b(N);
	vector<int> c(N, -1);
	dfs(0, g, in, vis, G, a, b, c);
	for (int u = 0; u < N; u++)
		if (c[u] == -1 && !vis[u]) {
			cout << -1 << endl;
			return 0;
		}
	vector<int> hoge;
	for (int u = 0; u < N; u++)
		if (c[u] == -1)
			hoge.push_back(u);
	int n = hoge.size();
	vector<vector<int> > d(n, vector<int>(n, INF));
	for (int i = 0; i < n; i++) d[i][i] = 0;
	for (int i = 0; i < n; i++) {
		int u = hoge[i];
		for (int k = 0; k < G[u].size(); k++) {
			edge e = G[u][k];
			int j = lower_bound(hoge.begin(), hoge.end(), e.v) - hoge.begin();
			d[i][j] = min(d[i][j], e.w);
		}
	}
	for (int k = 0; k < n; k++)
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
	ll ans = 0;
	for (int u = 0; u < N; u++) {
		int v = (u + 1) % N;
		if (c[u] != -1 && c[v] != -1 && c[u] == c[v] && b[u].second < b[v].second) {
			ans += b[v].second - b[u].second;
			continue;
		}
		int s = a[u].first, t = b[v].first;
		ans += a[u].second + b[v].second;
		int i = lower_bound(hoge.begin(), hoge.end(), s) - hoge.begin();
		int j = lower_bound(hoge.begin(), hoge.end(), t) - hoge.begin();
		if (d[i][j] == INF) {
			cout << -1 << endl;
			return 0;
		}
		ans += d[i][j];
	}
	cout << ans << endl;
}

Measured memory_bytes: 15456