#include <iostream>
#include <vector>
#include <queue>

using std::vector;

const int kMaxWeight = 10;
const int kInf = 1e9;

void BFS(vector<vector<std::pair<int, int>>>& neighbours,
                int start, int n, int& ans, vector<vector<int>>& m) {
  vector<std::queue<int>> q(kMaxWeight * n + 1);
  vector<int> distance(n, kInf);
  vector<bool> used(n, false);
  distance[start] = 0;
  q[0].push(start);
  for (int num_of_q = 0; num_of_q <= kMaxWeight * n; ++num_of_q) {
    while (!q[num_of_q].empty()) {
      int open_v = q[num_of_q].front();
      q[num_of_q].pop();
      if (used[open_v]) {
        continue;
      }
      used[open_v] = true;
      for (auto to : neighbours[open_v]) {
        if (distance[to.first] != kInf and !used[to.first]) {
          ans = std::min(ans, m[open_v][to.first] + (distance[open_v] + distance[to.first]));  // cycle
        }
        if (distance[to.first] > m[open_v][to.first] + distance[open_v]) {  // upgrade best distance
          distance[to.first] = m[open_v][to.first] + distance[open_v];
          q[distance[to.first]].push(to.first);
        }
      }
    }
  }
}

//void remove(vector<std::pair<int, int>>& v, int first_value, int second_value) {
//  for (int i = 0; i < v.size(); ++i) {
//    if (v[i].first == first_value and v[i].second == second_value) {
//      std::swap(v[i], v[v.size() - 1]);
//      v.pop_back();
//      break;
//    }
//  }
//}

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int n, m;
  std::cin >> n >> m;
  std::vector<std::vector<int>> cheapest_edge(n, std::vector<int>(n, kInf));
  std::vector<std::vector<int>> sec_cheapest_edge(n, std::vector<int>(n, kInf));
  vector<vector<std::pair<int, int>>> neighbours(n);

  for (int k = 0; k < m; ++k) {
    int first, second, weight;
    std::cin >> first >> second >> weight;
    if (cheapest_edge[first - 1][second - 1] > weight) {
      sec_cheapest_edge[second - 1][first - 1] = cheapest_edge[second - 1][first - 1];
      sec_cheapest_edge[first - 1][second - 1] = cheapest_edge[first - 1][second - 1];
      cheapest_edge[first - 1][second - 1] = weight;
      cheapest_edge[second - 1][first - 1] = weight;
    } else if (sec_cheapest_edge[first - 1][second - 1] > weight) {
      sec_cheapest_edge[second - 1][first - 1] = weight;
      sec_cheapest_edge[first - 1][second - 1] = weight;
    }
    neighbours[first - 1].push_back({second - 1, weight});
    neighbours[second - 1].push_back({first - 1, weight});
  }

  int answer = kInf;
  for (int v = 0; v < n; ++v) {
    BFS(neighbours, v, n, answer, cheapest_edge);
  }

  for (int i = 0; i < n; ++i) {
    for(int k = 0; k < n; ++k){
      if (answer > sec_cheapest_edge[i][k] + cheapest_edge[i][k]) {
        answer = sec_cheapest_edge[i][k] + cheapest_edge[i][k];  // simple cycle
      }
    }
  }
  std::cout << answer << "\n";
}