#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct E {
	int v, w, id;
};
struct C {
	vector<int> n, e;
	int v1;
	ll w0, w1, mw;
	vector<ll> y, d;
};
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m;
	cin >> n >> m;
	vector<vector<E>> g(n + 1);
	vector<ll> ew(m);
	ll tw = 0;
	vector<int> d(n + 1, 0);
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u].push_back({v, w, i});
		g[v].push_back({u, w, i});
		ew[i] = w;
		tw += w;
		d[u]++;
		d[v]++;
	}
	vector<int> tin(n + 1, 0);
	vector<pair<int, int>> stk;
	vector<bool> ic(m, false);
	vector<C> cs;
	int t = 0;
	auto dfs_c = [&](auto self, int u, int pid) -> void {
		tin[u] = ++t;
		stk.push_back({u, pid});
		for (auto& e : g[u]) {
			if (e.id == pid) continue;
			if (tin[e.v]) {
				if (tin[e.v] < tin[u]) {
					C c;
					c.v1 = e.v;
					for (int i = stk.size() - 1; stk[i].first != e.v; i--) {
						c.n.push_back(stk[i].first);
						c.e.push_back(stk[i].second);
						ic[stk[i].second] = true;
					}
					c.n.push_back(e.v);
					c.e.push_back(e.id);
					ic[e.id] = true;
					reverse(c.n.begin(), c.n.end());
					reverse(c.e.begin(), c.e.end());
					rotate(c.e.begin(), c.e.begin() + 1, c.e.end());
					cs.push_back(c);
				}
			} else {
				self(self, e.v, e.id);
			}
		}
		stk.pop_back();
	};
	dfs_c(dfs_c, 1, -1);
	vector<int> so(n + 1, 0);
	vector<bool> vis(n + 1, false);
	ll be = 0;
	auto dfs_o = [&](auto self, int u, int pid) -> void {
		vis[u] = true;
		so[u] = (d[u] % 2);
		for (auto& e : g[u]) {
			if (e.id == pid || ic[e.id]) continue;
			if (!vis[e.v]) {
				self(self, e.v, e.id);
				so[u] ^= so[e.v];
				if (so[e.v]) be += e.w;
			}
		}
	};
	dfs_o(dfs_o, 1, -1);
	for (auto& c : cs) {
		for (int v : c.n) if (!vis[v]) dfs_o(dfs_o, v, -1);
		int k = c.n.size();
		vector<int> p(k);
		for (int i = 0; i < k; i++) p[i] = so[c.n[i]];
		if (c.v1 != 1) p[0] ^= 1;
		c.y.resize(k);
		c.y[0] = p[0];
		for (int i = 1; i < k - 1; i++) c.y[i] = c.y[i - 1] ^ p[i];
		c.y[k - 1] = 0;
		c.w0 = 0;
		c.w1 = 0;
		for (int i = 0; i < k; i++) {
			c.w0 += ew[c.e[i]] * c.y[i];
			c.w1 += ew[c.e[i]] * (1 - c.y[i]);
		}
		c.mw = min(c.w0, c.w1);
		c.d.resize(k + 1, 0);
		for (int i = 0; i < k; i++) {
			c.d[i + 1] = c.d[i] + ew[c.e[i]] * (1 - 2 * c.y[i]);
		}
		if (c.v1 != 1) {
			for (int i = 1; i < k; i++) so[c.v1] ^= so[c.n[i]];
		}
	}
	vector<ll> f(n + 1, 0);
	vector<bool> vg(n + 1, false);
	ll ce = 0;
	for (auto& c : cs) ce += c.mw;
	ll mg = 0;
	vector<int> n2c(n + 1, -1);
	for (int i = 0; i < (int)cs.size(); i++) {
		for (int v : cs[i].n) n2c[v] = i;
	}
	vector<bool> cv(cs.size(), false);
	auto dfs_g = [&](auto self, int u) -> void {
		vg[u] = true;
		mg = min(mg, f[u]);
		if (n2c[u] != -1) {
			int ci = n2c[u];
			if (!cv[ci]) {
				cv[ci] = true;
				auto& c = cs[ci];
				int k = c.n.size();
				int p1 = 0;
				for (int i = 0; i < k; i++) if (c.n[i] == u) p1 = i;
				for (int i = 0; i < k; i++) {
					int v = c.n[i];
					if (v == u) continue;
					ll di = (i >= p1) ? (c.d[i] - c.d[p1]) : (c.d[k] - c.d[p1] + c.d[i]);
					f[v] = f[u] + min(c.w0 + di, c.w1 - di) - c.mw;
				}
				for (int v : c.n) {
					vg[v] = true;
					mg = min(mg, f[v]);
				}
				for (int v : c.n) {
					for (auto& e : g[v]) {
						if (!vg[e.v] && !ic[e.id]) {
							f[e.v] = f[v] + e.w * (1 - 2 * so[e.v]);
							self(self, e.v);
						}
					}
				}
			}
		}
		for (auto& e : g[u]) {
			if (!vg[e.v] && !ic[e.id]) {
				f[e.v] = f[u] + e.w * (1 - 2 * so[e.v]);
				self(self, e.v);
			}
		}
	};
	dfs_g(dfs_g, 1);
	cout << tw + be + ce + mg << endl;
	return 0;
}

```