#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<cstdio>
#include<climits>
#include<cmath>
#include<cstring>
#include<string>
#include<sstream>
#include<numeric>
#include<cassert>

#define f first
#define s second
#define mp make_pair

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define rep(i,s,n) for(int i=(s); i<(int)(n); i++)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define ALL(c) (c).begin(), (c).end()
#define IN(x,s,g) ((x) >= (s) && (x) < (g))
#define ISIN(x,y,w,h) (IN((x),0,(w)) && IN((y),0,(h)))
#define print(x) printf("%d\n",x)

using namespace std;

typedef unsigned int uint;
typedef long long ll;

const int _dx[] = {0,1,0,-1};
const int _dy[] = {-1,0,1,0};

int getInt(){
  int ret = 0,c;
  c = getchar();
  while(!isdigit(c)) c = getchar();
  while(isdigit(c)){
    ret *= 10;
    ret += c - '0';
    c = getchar();
  }
  return ret;
}

vector<vector<pair<int, int> > > g;
vector<int> in;
vector<int> out;
vector<bool> ok;
vector<int> id;
vector<int> from;
vector<long long> fromdist;
vector<int> to;
vector<long long> todist;
vector<vector<pair<int, long long> > > dist;
vector<vector<long long> > dijk;

int un;

class UnionFind{
private:
  vector<int> id;

  int getId(int i){
    if(i == id[i]) return i;
    return id[i] = getId(id[i]);
  }
public:
  UnionFind(int size = 0){ init(size); }
  ~UnionFind(){}
  void init(int size){
    id = vector<int>(size);
    for(int i = 0; i < size; i++)
      id[i] = i;
  }
  void unite(int i, int j){
    int next = min( getId(i), getId(j) );
    id[getId(i)] = id[getId(j)] = next;
  }
  int operator [](int i){ return getId(i); }
  int count(){
    set<int> s;
    for(int i = 0; i < (int)id.size(); i++)
      s.insert(getId(i));
    return s.size();
  }
};

UnionFind uf;

int init;
ll dis;

pair<int, long long> dfs(int pos, bool first = true){
  if((!first || pos != init) && ok[pos]){
    dist[id[init]].push_back(mp(id[pos], dis));
    return mp(pos, dis);
  }

  if(!ok[pos]){
    from[id[pos]]     = init;
    fromdist[id[pos]] = dis;
  }

  pair<int, int> last;
  for(int i = 0; i < (int)g[pos].size(); i++){
    int next = g[pos][i].f;
    ll d = g[pos][i].s;

    if(first) un = next;

    dis += d;
    last = dfs(next, false);
    dis -= d;

    if(!ok[pos]){
      uf.unite(id[pos], id[un]);
      to[id[pos]]     = last.first;
      todist[id[pos]] = last.second - dis;
    }
  }

  return last;
}

int main(){
  int n = getInt();
  int m = getInt();

  g = vector<vector<pair<int, int> > >(n);
  in = vector<int>(n);
  out = vector<int>(n);
  ok = vector<bool>(n, false);
  id = vector<int>(n);

  REP(i,m){
    int a = getInt() - 1;
    int b = getInt() - 1;
    int c = getInt();

    bool find = false;
    for(int i = 0; i < g[a].size(); i++){
      if(g[a][i].f == b){
        find = true;
        g[a][i].s = min(g[a][i].s, c);
      }
    }

    if(!find){
      g[a].push_back(mp(b, c));
      in[b]++;
      out[a]++;
    }
  }

  map<int, int> okid;
  map<int, int> trid;

  REP(i,n){
    if(in[i] == 0 || out[i] == 0){
      puts("-1");
      return 0;
    }
    if(in[i] == 1 && out[i] == 1){
      // trivial
      int id2 = trid.size();
      trid[id2] = i;
      id[i] = id2;
    }else{
      // non-trivial
      int id2 = okid.size();
      okid[id2] = i;
      ok[i] = true;
      id[i] = id2;
    }
  }

  // REP(i,n) printf("%d: %d\n", i, (int)ok[i]);

  int N = okid.size();
  int M = trid.size();
  const long long MAX = (1ll << 60);
  long long ans = 0;

  if(N == 0){
    vector<ll> memo(n);

    int cnt = 0;
    int now = 0;
    ll d = 0;
    while(cnt != n){
      if(cnt != 0 && 0 == now){
        puts("-1");
        return 0;
      }
      cnt++;
      d += g[now][0].s;
      now = g[now][0].f;
      memo[now] = d;
    }

    for(int i = 0; i < n; i++){
      int j = i == n - 1 ? 0 : i + 1;

      if(memo[j] > memo[i])
        ans += memo[j] - memo[i];
      else
        ans += memo[0] - memo[i] + memo[j];
    }
    printf("%lld\n", ans);
    return 0;
  }

  // printf("N: %d\n", N);
  if(N > 1000) return 0;

  dist = vector<vector<pair<int, ll> > >(N);
  dijk = vector<vector<ll> >(N, vector<ll>(N, -1));

  to = vector<int>(M, -1);
  from = vector<int>(M, -1);

  todist = vector<ll>(M);
  fromdist = vector<ll>(M);

  uf.init(M);

  REP(i,n) if(ok[i]){
    init = i;
    dfs(i);
  }

  //REP(k,N) REP(i,N) REP(j,N)
  //  dist[i][j] = min((long long)dist[i][j], (long long)dist[i][k] + dist[k][j]);

  REP(i,N){
    typedef pair<long long, int> data;
    priority_queue<data, vector<data>, greater<data> > pq;
    pq.push(mp(0, i));
    int cnt = 0;

    while(!pq.empty() && cnt != N){
      data d = pq.top(); pq.pop();
      long long ds = d.f;
      int pos = d.s;

      if(dijk[i][pos] != -1) continue;
      dijk[i][pos] = ds;
      cnt++;

      for(int j = 0; j < dist[pos].size(); j++){
        int next     = dist[pos][j].f;
        long long dd = ds + dist[pos][j].s;

        if(dijk[i][next] == -1){
          pq.push(mp(dd, next));
        }
      }
    }
  }

  REP(i,N) REP(j,N) if(dijk[i][j] == -1){
    puts("-1");
    return 0;
  }

  if(N != 0){
    REP(i,M) if(from[i] == -1 || to[i] == -1){
      puts("-1");
      return 0;
    }
  }


  // REP(i,N){ REP(j,N) printf("%4d ", (int)dijk[i][j]); puts(""); }

  for(int j = 0; j < n; j++){
    int prev = j;
    int next = j == n - 1 ? 0 : j + 1;
    long long tmp = 0;

    if(!ok[prev] && !ok[next] && uf[id[prev]] == uf[id[next]] && fromdist[id[prev]] < fromdist[id[next]]){
      tmp += fromdist[id[next]] - fromdist[id[prev]];
    }else{
      if(!ok[prev]){
        tmp += todist[id[prev]];
        prev = to[id[prev]];
      }

      if(!ok[next]){
        tmp += fromdist[id[next]];
        next = from[id[next]];
      }

      tmp += dijk[id[prev]][id[next]];
    }

    // printf("%d => %d: %lld\n", j + 1, 1 + (j == n - 1 ? 0 : j + 1), tmp);

    ans += tmp;
  }

  printf("%lld\n", ans);
  return 0;

}

Measured memory_bytes: 23000