#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define inf 0x3f3f3f3f
const int N = 5e5 + 5;
int n, m;
int tmp, dfn[N], low[N];
vector<pii> g[N << 1];
// 无向图缩点
// 求边双连通分量，注意可能出现重边
// 标记桥边
map<pii, bool> mp;
void dfs(int u, int las)
{
    dfn[u] = low[u] = ++tmp;
    for (auto [v, w] : g[u])
    {
        if (dfn[v] == 0)
        {
            dfs(v, w);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u])
                mp[{u, v}] = 1, mp[{v, u}] = 1;
        }
        else if (w != (las ^ 1))
            low[u] = min(low[u], dfn[v]);
    }
}

int vis[N], cnt, col[N], w[N], in[N];
vector<int> G[N];
void dfs2(int u)
{
    col[u] = cnt;
    w[cnt] += in[u];
    for (auto [v, w] : g[u])
    {
        if (vis[v]) continue;
        if (mp[{u, v}] || mp[{v, u}]) continue;
        vis[v] = 1;
        dfs2(v);
    }
}

struct node
{
    int u, v, w;
    bool operator<(const node& t)
    {
        return w < t.w;
    }
}e[N];

int minn = inf;
int siz[N];
map<pii, int>bq;
void dfs4(int u, int f)
{
    siz[u] = w[u];
    for (auto v: G[u])
    {
        if (v == f) continue;
        dfs4(v, u);
        siz[u] += siz[v] + 1;
        if (!(siz[v] & 1)) minn = min(minn, bq[{u, v}]);
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    int sum = 0;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        sum += w;
        in[u]++, in[v]++;
        e[i] = {u, v, w};
        g[u].push_back({v, i << 1}),
        g[v].push_back({u, i << 1 | 1});
    }
    if (m % 2 == 0)
    {
        cout << sum << endl;
        return 0;
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i]) dfs(i, 0);

    int ans = inf;
    for (int i = 1; i <= n; i++)
    {
        if (vis[i] == 0)
        {
            cnt++;
            vis[i] = 1;
            dfs2(i);
        }
    }
    for (int i = 1; i <= cnt; i++) w[i] = (w[i] + 1) / 2 - 1;
    for (int i = 1; i <= m; i++)
    {
        auto [u, v, w] = e[i];
        if (mp[{u, v}] == 0) ans = min(ans, w);
        else 
        {
            u = col[u], v = col[v];
            bq[{u, v}] = w;
            G[u].push_back(v),
            G[v].push_back(u);
        }
    }
    dfs4(1, 0);

    ans = min(ans, minn);
    cout << sum - ans << endl;
    return 0;
}