#include #include #include #include using namespace std; using int64 = long long; using pll = pair; struct edge { int64 cost, to; }; const int64 INF = 1ll << 60ll; const int64 MINF = -1 * (1ll << 60ll); int64 n, m; vector graph[32]; priority_queue p_que; int64 a, b, c; int64 ans; int64 max_cost[32]; int main() { scanf("%lld %lld", &n, &m); for (int64 i = 0; i < m; i++) { scanf("%lld %lld %lld", &a, &b, &c); c = -c; graph[a].emplace_back((struct edge){.cost = c, .to = b}); graph[b].emplace_back((struct edge){.cost = c, .to = a}); } for (int64 i = 1; i <= n; i++) { for (int64 j = 1; j <= n; j++) max_cost[j] = MINF; max_cost[i] = INF; p_que.push(pll(0, i)); while (!p_que.empty()) { pll state = p_que.top(); p_que.pop(); int64 cost = state.first; int64 pos = state.second; for (int64 j = 0; j < graph[pos].size(); j++) { int64 to = graph[pos][j].to; int64 nc = cost + graph[pos][j].cost; if (max_cost[to] < nc) { max_cost[to] = nc; p_que.push(pll(nc, to)); } } } for (int i = 1; i <= n; i++) { if (max_cost[i] != MINF) { ans = max(ans, -max_cost[i]); } } } printf("%lld\n", ans); return 0; }