#include <bits/stdc++.h>
#define INF 2e9
#define ll long long
using namespace std;
const int N = 1e5 + 3;
const int M = N + 1005;
const int CN = 2005;
const int CM = 3005;

inline int read() {
	char ch = getchar(); int x = 0;
	while (!isdigit(ch)) {ch = getchar();}
	while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
	return x;
}

struct node {
	int x, y, v;
}e[M];
struct Node {
	int x, disl, disr;
	Node(int a = 0, int b = 0, int c = 0) {x = a; disl = b; disr = c;}
};
ll ans, pdis[N], sdis[N];
int n, m, cnt, id[N], du[N], sz[N], qu[CN], mem[CN][CN], pcnt[N], scnt[N];
map<int, int> mp[N];
vector< pair<int, int> > g[N], G[N], E;
queue<int> q;
vector<Node> vec[CN][CN];
priority_queue< pair<int, int> > pq;
bitset<CN> in;

void dij(int st) {
	in.reset();
	for (int i = 1; i <= cnt; ++i) mem[st][i] = INF;
	mem[st][st] = 0; pq.push(make_pair(-mem[st][st], st));
	while (!pq.empty()) {
		int x = pq.top().second; pq.pop();
		if (in[x]) continue;
		in[x] = true;
		for (auto tmp : G[x]) {
			int y = tmp.first;
			if (mem[st][y] > mem[st][x] + tmp.second) {
				mem[st][y] = mem[st][x] + tmp.second;
				pq.push(make_pair(-mem[st][y], y));
			}
		}
	}
}

int main() {
	n = read(); m = read();
	for (int i = 1; i <= n; ++i) sz[i] = 1;
	for (int i = 1, x, y, v; i <= m; ++i) {
		x = read(); y = read(); v = read();
		if (mp[x].count(y) && e[mp[x][y]].v <= v) continue;
		else if (!mp[x].count(y)) du[x]++, du[y]++;
		e[i].x = x; e[i].y = y; e[i].v = v;
		mp[x][y] = mp[y][x] = i;
	}
	for (int i = 1; i <= n; ++i)
		if (du[i] <= 1) q.push(i);
	while (!q.empty()) {
		int x = q.front(); q.pop();
		if (du[x] == 0) continue;
		else {
			int y = (*mp[x].begin()).first, i = mp[x][y];
			mp[x].erase(y); mp[y].erase(x);
			du[x]--; du[y]--;
			if (du[y] <= 1) q.push(y);
			ans += 1ll * sz[x] * sz[y] * e[i].v;
			sz[x] += sz[y];
		}
	}
	for (int x = 1; x <= n; ++x)
		for (auto tmp : mp[x])
			g[x].push_back(make_pair(tmp.first, e[tmp.second].v));
	for (int x = 1; x <= n; ++x) {
		if (du[x] <= 2) continue;
		id[x] = ++cnt; qu[cnt] = x;
	}
	
	
	if (cnt == 0) {
		int st = 0;
		for (int i = 1; i <= n; ++i)
			if (du[i] == 2) {st = i; break;}
		if (st == 0) return printf("%lld\n", ans), 0;
		int x = st, pre = 0;
		vector< pair<int, int> > now;
		while (x != st) {
			pair<int, int> Mem;
			if (now.empty()) Mem = g[x][0];
			else if (g[x][0].first == now.back().first) Mem = g[x][1];
			else Mem = g[x][0];
			now.push_back(make_pair(x, pre));
			x = Mem.first; pre += Mem.second;
		}
		int p = 0;
		int cntdn = 0, cntup = 0;
		ll disdn = 0, disup = 0;
		for (int i = 0; i < now.size(); ++i) {
			while (p < now.size() && now[i].second - now[p].second > pre / 2) {
				cntup += sz[now[p].first]; disup += 1ll * sz[now[p].first] * now[p].second;
				cntdn -= sz[now[p].first]; disdn -= 1ll * sz[now[p].first] * now[p].second;
			}
			ans += (1ll * cntdn * now[i].second - disdn) * sz[now[i].first];
			ans += (1ll * cntup * (pre - now[i].first) + disup) * sz[now[i].first];
			cntdn += sz[now[i].first];
			disdn += 1ll * sz[now[i].first] * now[i].second;
		}
		return printf("%lld\n", ans), 0;
	}
	
	
	
	vector< pair<int, int> > tmp;
	for (int i = 1; i <= cnt; ++i) {
		int x = qu[i];
		for (auto o : g[x]) {
			tmp.clear();
			int y = o.first, sum = o.second;
			while (du[y] == 2) {
				pair<int, int> now;
				if (!tmp.empty() && g[y][0].first == tmp.back().first) now = g[y][1];
				else now = g[y][0];
				tmp.push_back(make_pair(y, sum));
				sum += now.second;
				y = now.first;
			}
			if (id[x] > id[y]) continue;
			G[id[x]].push_back(make_pair(id[y], sum));
			G[id[y]].push_back(make_pair(id[x], sum));
			E.push_back(make_pair(id[x], id[y]));
			for (auto p : tmp) vec[id[x]][id[y]].push_back(Node(p.first, p.second, sum - p.second));
		}
	}
	for (int i = 1; i <= cnt; ++i) dij(i);
	for (int i = 2; i <= cnt; ++i)
		for (int j = 1; j < i; ++j)
			ans += 1ll * sz[qu[i]] * sz[qu[j]] * mem[i][j];
	for (int i = 1; i <= cnt; ++i)
		for (auto j : E) for (auto y : vec[j.first][j.second])
			ans += 1ll * sz[qu[i]] * sz[y.x] * min(mem[i][j.first] + y.disl, mem[i][j.second] + y.disr);
	for (auto i : E) {
		int l = i.first, r = i.second;
		if (vec[l][r].empty()) continue;
		int cntup = 0; ll disup = 0;
		int cntdn = 0; ll disdn = 0;
		int p = 0;
		for (int j = 0; j < vec[l][r].size(); ++j) {
			while (p < vec[l][r].size() && vec[l][r][j].disl - vec[l][r][p].disl > vec[l][r][j].disr + vec[l][r][p].disl + mem[l][r]) {
				cntup += sz[vec[l][r][p].x]; disup += 1ll * sz[vec[l][r][p].x] * vec[l][r][p].disl;
				cntdn -= sz[vec[l][r][p].x]; disdn -= 1ll * sz[vec[l][r][p].x] * vec[l][r][p].disl;
				p++;
			}
			ans += 1ll * sz[vec[l][r][j].x] * (1ll * cntup * (mem[l][r] + vec[l][r][j].disr) + disup);
			ans += 1ll * sz[vec[l][r][j].x] * (1ll * cntdn * vec[l][r][j].disl - disdn);
			cntdn += sz[vec[l][r][j].x]; disdn += 1ll * sz[vec[l][r][j].x] * vec[l][r][j].disl;
		}
	}
	for (int idi = 0; idi < E.size(); ++idi) {
		auto i = E[idi];
		int li = i.first, ri = i.second;
		if (vec[li][ri].empty()) continue;
		pcnt[0] = sz[vec[li][ri][0].x];
		pdis[0] = 1ll * sz[vec[li][ri][0].x] * vec[li][ri][0].disl;
		for (int p = 1; p < vec[li][ri].size(); ++p) {
			pcnt[p] = pcnt[p - 1] + sz[vec[li][ri][p].x];
			pdis[p] = pdis[p - 1] + 1ll * sz[vec[li][ri][p].x] * vec[li][ri][p].disl;
		}
		scnt[vec[li][ri].size()] = sdis[vec[li][ri].size()] = 0;
		for (int p = vec[li][ri].size() - 1; p >= 0; --p) {
			scnt[p] = scnt[p + 1] + sz[vec[li][ri][p].x];
			sdis[p] = sdis[p + 1] + 1ll * sz[vec[li][ri][p].x] * vec[li][ri][p].disr;
		}
		
		for (int idj = idi + 1; idj < E.size(); ++idj) {
			auto j = E[idj];
			int lj = i.first, rj = j.second;
			if (vec[lj][rj].empty()) continue;
			int p = 0;
			while (p < vec[lj][rj].size() && vec[lj][rj][p].disl + mem[li][lj] < vec[lj][rj][p].disr + mem[li][rj]) p++;
			int q = 0;
			while (q < vec[lj][rj].size() && vec[lj][rj][p].disl + mem[ri][lj] < vec[lj][rj][p].disr + mem[ri][rj]) p++;
			
			
			int cnt; ll sum;
			
			
			
			cnt = 0; sum = 0;
			for (int k = 0; k < min(p, q); ++k) {
				cnt += sz[vec[lj][rj][k].x];
				sum += 1ll * sz[vec[lj][rj][k].x] * vec[lj][rj][k].disl;
			}
			
			auto check = [&](int l, int r, int oo, int lim) {return vec[l][r][oo].disr - vec[l][r][oo].disl >= lim;};
			auto find = [&](int l, int r, int lim) {
				if (!check(l, r, 0, lim)) return -1;
				int L = 0, R = vec[l][r].size() - 1, mid;
				while (L + 1 < R) {
					mid = (L + R) >> 1;
					if (check(l, r, mid, lim)) L = mid;
					else R = mid;
				}
				if (check(l, r, R, lim)) return R;
				else return L;
			};
			int o = find(li, ri, mem[li][lj] - mem[ri][lj]);
			ans += 1ll * pcnt[o] * cnt * mem[li][lj];
			ans += 1ll * pcnt[o] * sum + 1ll * pdis[o] * cnt;
			ans += 1ll * scnt[o + 1] * cnt * mem[ri][lj];
			ans += 1ll * scnt[o + 1] * sum + 1ll * sdis[o + 1] * cnt;
			
			
			
			if (p < q) {
				int K = 0;
				for (int k = p; k < q; ++k) {
					while (K < vec[li][ri].size()) {
						int len1 = vec[li][ri][K].disl + mem[li][rj] + vec[lj][rj][k].disr;
						int len2 = vec[li][ri][K].disr + mem[ri][lj] + vec[lj][rj][k].disl;
						if (len1 >= len2) break;
						K++;
					}
					if (K) {
						ans += 1ll * pcnt[K - 1] * sz[vec[lj][rj][k].x] * mem[li][rj];
						ans += 1ll * pcnt[K - 1] * sz[vec[lj][rj][k].x] * vec[lj][rj][k].disr;
						ans += 1ll * pdis[K - 1] * sz[vec[lj][rj][k].x];
					}
					ans += 1ll * scnt[K] * sz[vec[lj][rj][k].x] * mem[ri][lj];
					ans += 1ll * scnt[K] * sz[vec[lj][rj][k].x] * vec[lj][rj][k].disl;
					ans += 1ll * sdis[K] * sz[vec[lj][rj][k].x];
				}
			}else {
				int K = vec[li][ri].size() - 1;
				for (int k = q; k < p; ++k) {
					while (K >= 0) {
						int len1 = vec[li][ri][K].disr + mem[ri][rj] + vec[lj][rj][k].disr;
						int len2 = vec[li][ri][K].disl + mem[li][lj] + vec[lj][rj][k].disl;
						if (len1 >= len2) break;
						K--;
					}
					if (K >= 0) {
						ans += 1ll * pcnt[K] * sz[vec[lj][rj][k].x] * mem[li][lj];
						ans += 1ll * pcnt[K] * sz[vec[lj][rj][k].x] * vec[lj][rj][k].disl;
						ans += 1ll * pdis[K] * sz[vec[lj][rj][k].x];
					}
					ans += 1ll * scnt[K + 1] * sz[vec[lj][rj][k].x] * mem[ri][rj];
					ans += 1ll * scnt[K + 1] * sz[vec[lj][rj][k].x] * vec[lj][rj][k].disr;
					ans += 1ll * sdis[K + 1] * sz[vec[lj][rj][k].x];
				}
			}
			
			
			cnt = 0; sum = 0;
			for (int k = max(p, q); k < vec[lj][rj].size(); ++k) {
				cnt += sz[vec[lj][rj][k].x];
				sum += 1ll * sz[vec[lj][rj][k].x] * vec[lj][rj][k].disr;
			}
			o = find(li, ri, mem[li][rj] - mem[ri][rj]);
			ans += 1ll * pcnt[o] * cnt * mem[li][rj];
			ans += 1ll * pcnt[o] * sum + 1ll * pdis[o] * cnt;
			ans += 1ll * scnt[o + 1] * cnt * mem[ri][rj];
			ans += 1ll * scnt[o + 1] * sum + 1ll * sdis[o + 1] * cnt;
			
			
		}
	}
	
	return printf("%lld\n", ans), 0;
}