#include<iostream>
#include<stdio.h>
using namespace std;

#define INF 100000000

int main(){
  int N,M;
  cin >> N >> M;
  int glaf[N+1][N+1];
  for(int i=0;i<=N;i++){
    for(int j=0;j<=N;j++){
      glaf[i][j] = INF;
    }
    glaf[i][i] = 0;
  }

  int s,t,d;
  for(int i=0;i<M;i++){
    cin >> s >> t >> d;
    glaf[s][t] = min(d,glaf[s][t]);
  }

  for(int k=1;k<=N;k++)
    for(int i=1;i<=N;i++)
      for(int j=1;j<=N;j++)
        glaf[i][j] = min(glaf[i][j],glaf[i][k]+glaf[k][j]);

  int ans = 0;
  for(int i=1;i<=N;i++){
    int g = (i==N) ? 1 : i+1;
    if(glaf[i][g]==INF){
      cout << -1 << endl;
      return 0;
    }
    ans += glaf[i][g];
  }
  // for(int i=1;i<=N;i++){
  //   for(int j=1;j<=N;j++)
  //     printf("%3d ",glaf[i][j]);
  //   cout << endl;
  // }
  cout << ans << endl;

  return 0;
}

