#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define DEBUG 0
#define MAXN 18

using namespace std;

struct Edge{
  int a, b, cost;

  bool operator>(const Edge& other) const{
    return cost > other.cost;
  }
};
vector<vector<Edge>> v, u;

priority_queue<Edge, vector<Edge>, std::greater<Edge>> pq;
int dv[MAXN], du[MAXN];

int main(){
  int n, m;

  ifstream fin ("hamilton.in");
  fin >> n >> m;
  v.resize(n);
  u.resize(n);

  for(int i = 0; i < m; i ++){
    int a, b, c;
    fin >> a >> b >> c;
    v[a].push_back({a, b, c});
    u[b].push_back({b, a, c});
  }
  fin.close();

  for(int i = 0; i < n; i ++)
    dv[i] = du[i] = -1;

  pq.push({0, 0, 1});
  while(!pq.empty()){
    Edge e = pq.top();
    pq.pop();
    if(dv[e.b] == -1){
      dv[e.b] = dv[e.a] + e.cost;

      for(int i = 0; i < v[e.b].size(); i ++){
        pq.push(v[e.b][i]);
      }
    }
  }

  pq.push({0, 0, 1});
  while(!pq.empty()){
    Edge e = pq.top();
    pq.pop();
    if(du[e.b] == -1){
      du[e.b] = du[e.a] + e.cost;

      for(int i = 0; i < u[e.b].size(); i ++){
        pq.push(u[e.b][i]);
      }
    }
  }

  int sum = 0;
  for(int i = 0; i < n; i ++){
    if(DEBUG)
      printf("%d %d\n", dv[i], du[i]);
    if(dv[i] < du[i])
      sum += dv[i];
    else
      sum += du[i];
  }

  ofstream fout ("hamilton.out");
  fout << sum << "\n";
  fout.close();

  return 0;
}