1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <set>
using namespace std;
// d odac do act_path
void find_heaviest_path_from_w(int  n, int w, vector<vector<pair<int,int64_t>>>& adj_list, set<pair<int,int>>& max_path,  vector<int>& actual_path, vector<bool>& was_here, int64_t cur_cost, int64_t& max_cost)  {
  if (was_here[w]) {
    return;
  }
  was_here[w] = true;

  if (n == 4)  {
    if (cur_cost > max_cost) {
      max_cost = cur_cost;
      max_path.clear();
      for (int i = 0; i < 4; ++i) {
        if ( actual_path[i] > actual_path[i + 1]) {
          max_path.insert(make_pair(actual_path[i + 1], actual_path[i]));

        } else {
          max_path.insert(make_pair(actual_path[i], actual_path[i + 1]));

        }
      }
    }
    return;
  }
  for (auto [v,cost]: adj_list[w]) {
    actual_path.push_back(v);
    find_heaviest_path_from_w(n + 1, v, adj_list, max_path, actual_path, was_here, cur_cost + cost, max_cost);
    actual_path.pop_back();
  }
}

bool func(tuple<int64_t, int, set<pair<int,int>>>a, tuple<int64_t, int, set<pair<int,int>>>b) {
  if (get<0>(a) == get<0>(b)) {
    return get<1>(a) <  get<1>(b);
        }
  return get<0>(a) < get<0>(b);
}

tuple<int64_t, int, set<pair<int,int>>> prepare_data(vector<vector<pair<int,int64_t>>>& adj_list, int n, int  w) {
  set<pair<int,int>> max_path;
  vector<int> actual_path(1,w);
  vector<bool> was_here(n, false);
  int64_t max_cost = 0;
  find_heaviest_path_from_w(0,w,adj_list,max_path,actual_path,was_here,0,max_cost);
  return make_tuple(max_cost, w, max_path);
}



int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);
  int n;
  cin >> n;
  vector<vector<pair<int,int64_t>>> adj_list(n);
  int v1, v2;
  int64_t cost;
  for (int i = 0; i < n; ++i) {
    cin >> v1 >> v2 >> cost;
    v1 -= 1;
    v2 -=1 ;
    adj_list[v1].push_back(make_pair(v2,cost));
    adj_list[v2].push_back(make_pair(v1,cost));
  }


  vector<tuple<int64_t, int, set<pair<int,int>>>> max_moneys;
  set<pair<int,int>> used_paths;
  int64_t  full_cost = 0;
  for (int i = 0; i < n; ++i) {
    auto k = prepare_data(adj_list,n,i);
    if  (get<0>(k) > 0) {
      max_moneys.push_back(k);
    }
  }
sort(max_moneys.begin(), max_moneys.end(), func);
  int flagger = 0;
  size_t len = max_moneys.size();
  if (len == 0) {
    cout << 0;
    return 0;
  }
  for (int64_t i = len - 1; i >= 0; --i) {
    flagger = false;
    auto cur_path = max_moneys[i];
    for (auto m: get<2>(cur_path)) {
      if (used_paths.find(m) != used_paths.end()) {
        flagger =true;
        break;
      }
    }
    if (flagger) {
      continue;
    }
    for (auto m: get<2>(cur_path)) {
      used_paths.insert(m);
    }
    full_cost += get<0>(cur_path);
  }
 cout << full_cost;

  return 0;
}