通过便利每两个点之间的传送门，再便利一次其他点与传送点的路长度，没路的情况是最大值不会考虑，有路就取经过传送门和原本最短路的最小值

/* 台州第一深情 */

include <bits/stdc++.h>

using namespace std;
using i64 = long;
using ll = long long;
typedef pair<int, int> PII;
const int N = 105 + 5;
const int M = 1e6;
ll a[N][N], b[M];
int n, m;
void build()
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (i == j)
{
a[i][j] = 0;
}
else
{
a[i][j] = 1e7;//模板，根据题目定义最大值
}
}
}
}
void floyd()
{
for (int tiao = 1; tiao <= n; tiao++)
{
for (int from = 1; from <= n; from++)
{
for (int to = 1; to <= n; to++)
{
a[from][to] = min(a[from][tiao] + a[tiao][to], a[from][to]);
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
build();
for (int i = 1; i <= m; i++)
{
int from, to, w;
cin >> from >> to >> w;
a[from][to] = w;
a[to][from] = w;//无向图，存双边
}
ll ans = INT_MAX;
floyd();//先确定正常情况下的最小值
for (int i = 1; i < n; i++)
{
for (int j = i + 1; j <= n; j++)//i,j是假设从哪个点到哪个点有传送门
{
ll p = 0;
for (int i1 = 1; i1 < n; i1++)//每确定一个传送门都进行一次floyd，便利查找最小值
{
for (int j1 = i1 + 1; j1 <= n; j1++)
{
if (i1 != i || j1 != j)
{
p += min(a[i1][j1], min(a[i1][i] + a[j][j1], a[i1][j] + a[i][j1]));//便利每个点与传送点是否有路，如果有的话就判断一下经过传送门到目标点是不是会更短
}
}
}
ans = min(ans, p);//取小
}
}
cout << ans << "\n";

return 0;

}