#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
//#define int ll
const int N = 25;
int a[N], b[N], c[N], d[N];
void add(int l, int r, int delta) {
d[l] += delta;
d[r + 1] -= delta;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
int ans = 0;
for (int i = 0; i < m; i++) {
cin >> a[i] >> b[i] >> c[i];
ans += c[i];
if (a[i] > b[i]) {
swap(a[i], b[i]);
}
}
for (int mask = 0; mask < (1 << m); mask++) {
for (int i = 0; i <= n; i++) {
d[i] = 0;
}
for (int i = 0; i < m; i++) {
if ((mask >> i) & 1) {
add(a[i], b[i] - 1, c[i]);
}
else {
add(1, a[i] - 1, c[i]);
add(b[i], n, c[i]);
}
}
int cur = 0, mx = 0;
for (int i = 1; i <= n; i++) {
cur += d[i];
mx = max(mx, cur);
}
ans = min(ans, mx);
}
cout << ans << '\n';
}
