#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <map>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

int n, m;
int q, r;
int matrix[1010][1010];
vector<pair<int, int> > g[100010];
vector<pair<int, int> > revG[100010];
bool visit[100010];
int mapto[100010];

int parent[100010];
int child[100010];
int lineNumber[100010];
int dist[100010];
int line[100010];

// calc revG
int dfs1(int from) {
  if (visit[from]) { return 0; }
  visit[from] = true;

  int ret = 1;
  FORIT(it, revG[from]) { ret += dfs1(it->first); }
  return ret;
}

// calc degree > 1 node
int dfs2(int from) {
  if (visit[from]) {
    if (mapto[from] == -1) { mapto[from] = q++; }
    return 0;
  }
  visit[from] = true;

  if (g[from].size() > 1 && mapto[from] == -1) {
    mapto[from] = q++;
  }

  int ret = 1;
  FORIT(it, g[from]) { ret += dfs2(it->first); }
  return ret;
}

// calc dist
int dfs3(int from, int p, int d, int number) {
  if (mapto[from] != -1) {
    lineNumber[from] = 0;
    line[number] = d;
    matrix[p][mapto[from]] = min(matrix[p][mapto[from]], d);
    p = mapto[from];
    d = 0;
  }

  if (visit[from]) {
    assert(mapto[from] != -1);
    return mapto[from];
  }
  visit[from] = true;

  int ret = -1;
  parent[from] = p;
  dist[from] = d;

  if (mapto[from] == -1) {
    lineNumber[from] = number;
  }

  FORIT(it, g[from]) {
    int nnumber = number;
    if (mapto[from] != -1) { nnumber = r++; }
    ret = dfs3(it->first, p, d + it->second, nnumber);
  }
  if (mapto[from] != -1) { ret = mapto[from]; }
  child[from] = ret;

  assert(ret != -1);
  return ret;
}

int main() {
  while (scanf("%d %d", &n, &m) > 0) {
    q = 0;
    MEMSET(mapto, -1);
    MEMSET(matrix, 0x0f);
    MEMSET(lineNumber, 0);
    MEMSET(line, 0);
    REP(i, n) { g[i].clear(); }
    REP(i, n) { revG[i].clear(); }
    map<pair<int, int>, int> edge;
    REP(i, m) {
      int f, t, c;
      scanf("%d %d %d", &f, &t, &c);
      f--; t--;
      pair<int, int> ft = make_pair(f, t);
      if (!edge.count(ft)) { edge[ft] = 10000; }
      edge[ft] = min(edge[ft], c);
    }
    FORIT(it, edge) {
      int f = it->first.first;
      int t = it->first.second;
      int c = it->second;
      g[f].push_back(make_pair(t, c));
      revG[t].push_back(make_pair(f, c));
    }

    MEMSET(visit, false);
    if (dfs1(0) != n) {
      printf("-1\n");
      continue;
    }

    MEMSET(visit, false);
    q = 0;
    mapto[0] = q++;
    if (dfs2(0) != n) {
      printf("-1\n");
      continue;
    }

    MEMSET(visit, false);
    r = 1;
    dfs3(0, mapto[0], 1 << 30, 0);
    line[0] = 0;
    REP(i, q) { matrix[i][i] = 0; }
    REP(k, q) REP(i, q) REP(j, q) {
      matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j]);
    }

    ll ans = 0;
    int prev = 0;
    REP(i, n) {
      int next = (i + 1) % n;
      int pl = lineNumber[prev];
      int nl = lineNumber[next];
      //int pp = parent[prev];
      int np = parent[next];
      int pc = child[prev];
      //int nc = child[next];
      ll pans = ans;
      if (pl == nl && dist[prev] < dist[next]) {
        ans += dist[next] - dist[prev];
      } else {
        ans += line[pl] - dist[prev];
        ans += matrix[pc][np];
        ans += dist[next];
      }
      assert(ans > pans);
      prev = next;
    }
    printf("%lld\n", ans);
  }
  return 0;
}

Measured memory_bytes: 17000