#include <bits/stdc++.h>  
using namespace std;  

#define int long long  

signed main() {  
    ios::sync_with_stdio(false);
    cin.tie(nullptr);  

	int n, m;
	cin >> n >> m;

	vector<vector<pair<int, int>>> adj(n + 1);
	vector<array<int, 3>> e;
	map<pair<int, int>, int> t;
	int sum = 0;
	for (int i = 1; i <= m; i++) {
		int x, y, w;
		cin >> x >> y >> w;
		sum += w;
		t[{x, y}] = w;
		t[{y, x}] = w;
		e.push_back({x, y, w});
		adj[x].push_back({y, w});
		adj[y].push_back({x, w});
	}

	if (m % 2 == 0) {
		cout << sum << "\n";
		return 0;
	}

	vector<int> low(n + 1), dfn(n + 1), fa(n + 1);
	set<pair<int, int>> br;
	int tim = 0;
	function<void(int, int)> dfs = [&](int x, int f) {
		fa[x] = f;
		low[x] = dfn[x] = ++tim;
		for (auto [y, w] : adj[x]) {
			if (!dfn[y]) {
				dfs(y, x);
				low[x] = min(low[x], low[y]);
				if (low[y] > dfn[x]) {
					br.insert({x, y});
					br.insert({y, x});
				}
			} else if (dfn[y] < dfn[x] && y != f) {
				low[x] = min(low[x], dfn[y]);
			}
		}
	};

	dfs(1, 0);

	sort(e.begin(), e.end(), [&](auto a, auto b) {
		return a[2] < b[2];
	});
 
	vector<int> cnt(n + 2), c(n + 1);
	for (int i = 1; i <= n; i++) {
		cnt[dfn[i]] = adj[i].size();
	}
	for (int i = n - 1; i >= 0; i--) {
		cnt[i] += cnt[i + 1];
	}
	for (int i = 1; i <= n; i++) {
		for (auto [y, w] : adj[i]) {
			if (dfn[y] > dfn[i]) {
				c[i]++;
			}
		}
	}

	for (auto [x, y, w] : e) {
		if (!br.count({x, y})) {
			cout << sum - w << "\n";
			return 0;
		} else {
			if (dfn[x] > dfn[y]) {
				swap(x, y);
			}
			// cout << x << " " << y << " " << dfn[y] << " " << cnt[dfn[y] + 1] << " " << c[y] << "\n"; 
			if ((cnt[dfn[y] + 1] + c[y]) / 2 % 2 == 0) {
				cout << sum - w << "\n";
				return 0;
			}
		}
	}

	assert(false);

    return 0;
}