#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 INF = 1e9 + 10;
const ll BINF = 1e18 + 10;
struct Flow {
struct edge {
int to, c, w, f;
};
vector<edge> arr;
vector<vector<int>> g;
vector<int> pnt;
vector<ll> potential;
vector<bool> used;
int n, m, s, t, cnt = 0;
Flow(int maxn, int maxm, int _s, int _t) {
n = maxn;
m = maxm;
s = _s;
t = _t;
arr.resize(m + 1);
g.resize(n + 1);
pnt.resize(n + 1);
potential.resize(n + 1);
used.resize(n + 1);
}
inline void add_edge(int from, int to, int c, int w = 0, int f = 0) {
arr[cnt] = {to, c, w, f};
g[from].pb(cnt++);
}
int Ford_Fulkerson_dfs(int v, int min_f, int need = 1) {
if (v == t) {
return min_f;
}
used[v] = true;
for (int u : g[v]) {
if (!used[arr[u].to] && arr[u].c - arr[u].f >= need) {
int val = Ford_Fulkerson_dfs(arr[u].to, min(min_f, arr[u].c - arr[u].f), need);
if (val >= need) {
arr[u].f += val;
arr[u ^ 1].f -= val;
return val;
}
}
}
return 0;
}
inline int Ford_Fulkerson() { //O(|F| * E)
int res = 0;
for (;;) {
fill(all(used), false);
int val = Ford_Fulkerson_dfs(s, INF);
if (!val) {
return res;
}
res += val;
}
}
inline int Ford_Fulkerson_with_scaling(int mx = INF) { //O(E^2 * log(U)), where U is the maximum capacity
int res = 0, up = (int)log2(mx);
for (int k = up; k >= 0; k--) {
for (;;) {
fill(all(used), false);
int val = Ford_Fulkerson_dfs(s, INF, 1 << k);
if (!val) {
break;
}
res += val;
}
}
return res;
}
inline int Edmonds_Karp_bfs(int need = 1) {
vector<pair<int, int>> from(n + 1);
fill(all(used), false);
queue<int> q;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
for (int u : g[v]) {
if (arr[u].c - arr[u].f >= need && !used[arr[u].to]) {
used[arr[u].to] = true;
q.push(arr[u].to);
from[arr[u].to] = {v, u};
}
}
}
if (!used[t]) {
return 0;
}
int now = t, min_f = INF;
while (now != s) {
min_f = min(min_f, arr[from[now].second].c - arr[from[now].second].f);
now = from[now].first;
}
now = t;
while (now != s) {
int ind = from[now].second;
arr[ind].f += min_f;
arr[ind ^ 1].f -= min_f;
now = from[now].first;
}
return min_f;
}
int Edmonds_Karp() { //O(VE^2)
int res = 0;
for (;;) {
int val = Edmonds_Karp_bfs();
if (!val) {
return res;
}
res += val;
}
}
int Edmonds_Karp_with_scaling(int mx = INF) { // O(E^2 * log(U)), where U is the maximum capacity
int res = 0, up = (int)log2(mx);
for (int k = up; k >= 0; k--) {
for (;;) {
int val = Edmonds_Karp_bfs(1 << k);
if (!val) {
break;
}
res += val;
}
}
return res;
}
int Dinic_dfs(int v, int min_f, int need = 1) {
if (v == t) {
return min_f;
}
used[v] = true;
for (; pnt[v] < SZ(g[v]); pnt[v]++) {
int u = g[v][pnt[v]];
if (!used[arr[u].to] && arr[u].c - arr[u].f >= need) {
int val = Dinic_dfs(arr[u].to, min(min_f, arr[u].c - arr[u].f), need);
if (val >= need) {
arr[u].f += val;
arr[u ^ 1].f -= val;
return val;
}
}
}
return 0;
}
inline int Dinic_bfs(int need = 1) {
vector<int> dist(n + 1, INF);
dist[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
for (auto u : g[v]) {
if (arr[u].c - arr[u].f >= need && dist[arr[u].to] == INF) {
dist[arr[u].to] = dist[v] + 1;
q.push(arr[u].to);
}
}
}
if (dist[t] == INF) {
return 0;
}
fill(all(pnt), 0);
int res = 0;
for (;;) {
fill(all(used), false);
int val = Dinic_dfs(s, INF, need);
if (!val) {
return res;
}
res += val;
}
}
int Dinic() { // O(V^2 * E), on single networks O(E * sqrt(E))
int res = 0;
for (;;) {
int val = Dinic_bfs();
if (!val) {
return res;
}
res += val;
}
}
int Dinic_with_scaling(int mx = INF) { // O(VE * log(U)), where U is the maximum capacity
int res = 0, up = (int)log2(mx);
for (int k = up; k >= 0; k--) {
for (;;) {
int val = Dinic_bfs(1 << k);
if (!val) {
break;
}
res += val;
}
}
return res;
}
inline ll Ford_Bellman() {
vector<ll> dist(n + 1, INF);
vector<pair<int, int>> from(n + 1);
vector<bool> already(n + 1, false);
dist[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
already[v] = false;
for (auto it : g[v]) {
if (dist[v] + arr[it].w < dist[arr[it].to] && arr[it].c > arr[it].f) {
dist[arr[it].to] = dist[v] + arr[it].w;
from[arr[it].to] = {v, it};
if (!already[arr[it].to]) {
q.push(arr[it].to);
already[arr[it].to] = true;
}
}
}
}
int now = t, mn = INF;
while (from[now].first) {
mn = min(mn, arr[from[now].second].c - arr[from[now].second].f);
now = from[now].first;
}
now = t;
while (from[now].first) {
arr[from[now].second].f += mn;
arr[from[now].second ^ 1].f -= mn;
now = from[now].first;
}
return dist[t] * mn;
}
void init_potentials() {
vector<ll> dist(n + 1, INF);
vector<bool> already(n + 1, false);
dist[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
already[v] = false;
for (auto it : g[v]) {
if (dist[v] + arr[it].w < dist[arr[it].to] && arr[it].c > arr[it].f) {
dist[arr[it].to] = dist[v] + arr[it].w;
if (!already[arr[it].to]) {
q.push(arr[it].to);
already[arr[it].to] = true;
}
}
}
}
for (int i = 1; i <= n; i++) {
if (dist[i] != INF) {
potential[i] = dist[i];
}
}
}
inline ll Dijkstra_with_potentials1() {
vector<ll> dist(n + 1, INF);
vector<pair<int, int>> from(n + 1);
dist[s] = 0;
set<pair<ll, int>> st;
for (int i = 1; i <= n; i++) {
st.insert({dist[i], i});
}
while (!st.empty()) {
int v = st.begin()->second;
st.erase(st.begin());
for (auto it : g[v]) {
int u = arr[it].to;
ll cost = arr[it].w + potential[v] - potential[u];
if (arr[it].f < arr[it].c && dist[v] + cost < dist[u]) {
st.erase({dist[u], u});
dist[u] = dist[v] + cost;
st.insert({dist[u], u});
from[u] = {v, it};
}
}
}
int now = t, mn = INF;
while (from[now].first) {
mn = min(mn, arr[from[now].second].c - arr[from[now].second].f);
now = from[now].first;
}
now = t;
while (from[now].first) {
arr[from[now].second].f += mn;
arr[from[now].second ^ 1].f -= mn;
now = from[now].first;
}
ll res = (dist[t] - potential[s] + potential[t]) * mn;
for (int i = 1; i <= n; i++) {
if (dist[i] < INF) {
potential[i] += dist[i];
}
}
return res;
}
inline ll Dijkstra_with_potentials2() {
vector<ll> dist(n + 1, INF);
vector<pair<int, int>> from(n + 1);
fill(all(used), false);
dist[s] = 0;
for (int i = 1; i <= n; i++) {
pair<int, int> best = {INF, INF};
for (int j = 1; j <= n; j++) {
if (!used[j]) {
best = min(best, {dist[j], j});
}
}
int v = best.second;
used[v] = true;
for (auto it : g[v]) {
int u = arr[it].to;
ll cost = arr[it].w + potential[v] - potential[u];
if (arr[it].f < arr[it].c && dist[v] + cost < dist[u]) {
dist[u] = dist[v] + cost;
from[u] = {v, it};
}
}
}
int now = t, mn = INF;
while (from[now].first) {
mn = min(mn, arr[from[now].second].c - arr[from[now].second].f);
now = from[now].first;
}
now = t;
while (from[now].first) {
arr[from[now].second].f += mn;
arr[from[now].second ^ 1].f -= mn;
now = from[now].first;
}
ll res = (dist[t] - potential[s] + potential[t]) * mn;
for (int i = 1; i <= n; i++) {
if (dist[i] < INF) {
potential[i] += dist[i];
}
}
return res;
}
ll mincost_with_FB(int flow_sz = INF) { // O(|F| * VE)
ll res = 0;
for (int i = 0; i < flow_sz; i++) {
ll val = Ford_Bellman();
if (val >= BINF) {
return res;
}
res += val;
}
return res;
}
ll mincost_with_Dijkstra1(int flow_sz = INF) {// O(|F| * E log V)
init_potentials();
ll res = 0;
for (int i = 0; i < flow_sz; i++) {
ll val = Dijkstra_with_potentials1();
if (val >= BINF) {
return res;
}
res += val;
}
return res;
}
ll mincost_with_Dijkstra2(int flow_sz = INF) { // O(|F| * V^2)
init_potentials();
ll res = 0;
for (int i = 0; i < flow_sz; i++) {
ll val = Dijkstra_with_potentials2();
if (val >= BINF) {
return res;
}
res += val;
}
return res;
}
};
const int N = 2e5 + 10;
int a[N], b[N], c[N], cap_in[N], cap_out[N];
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
map<pair<int, int>, int> edge;
int sum = 0;
for (int i = 1; i <= m; i++) {
cin >> a[i] >> b[i] >> c[i];
if (a[i] > b[i]) {
swap(a[i], b[i]);
}
sum += c[i];
cap_in[a[i]] += c[i];
cap_out[b[i]] += c[i];
edge[{a[i], b[i]}] += c[i];
}
int ptr = 0;
for (auto it : edge) {
a[++ptr] = it.F.F;
b[ptr] = it.F.S;
c[ptr] = it.S;
}
m = ptr;
int add = 0;
for (int i = 1; i <= n; i++) {
if (cap_in[i]) {
add++;
}
if (cap_out[i]) {
add++;
}
}
int l = 0, r = n;
while (r - l > 1) {
int mid = (l + r) / 2;
Flow F(n + 2, 2 * (2 * n + m + add), n + 1, n + 2);
for (int i = 1; i <= n; i++) {
if (cap_in[i]) {
F.add_edge(n + 1, i, cap_in[i]);
F.add_edge(i, n + 1, 0);
}
if (cap_out[i]) {
F.add_edge(i, n + 2, cap_out[i]);
F.add_edge(n + 2, i, 0);
}
}
for (int i = 1; i <= n; i++) {
int to = i + 1;
if (to == n + 1) {
to = 1;
}
F.add_edge(i, to, mid);
F.add_edge(to, i, 0);
F.add_edge(to, i, mid);
F.add_edge(i, to, 0);
}
if (F.Ford_Fulkerson() == sum) {
r = mid;
}
else {
l = mid;
}
}
cout << r << '\n';
}
