import sys
# Увеличиваем лимит рекурсии на всякий случай, хотя используем итеративный подход
sys.setrecursionlimit(200000)
def solve():
# Быстрый ввод
input = sys.stdin.read
data = input().split()
iterator = iter(data)
try:
N = int(next(iterator))
M = int(next(iterator))
except StopIteration:
return
requests = []
# Считываем запросы
for _ in range(M):
u = int(next(iterator))
v = int(next(iterator))
c = int(next(iterator))
if u == v:
continue
# Нормализуем путь как линейный отрезок [start, end)
# Билет i соединяет станции i и i+1.
# Станции нумеруются 1..N. Билеты 1..N.
# Путь от u до v по линейке (без перехода N-1) занимает билеты
# с индексами от min(u, v) до max(u, v) - 1.
# Индексы билетов делаем 0-based: 1 -> 0 ... N -> N-1
start = min(u, v)
end = max(u, v)
# Длина линейного пути
linear_len = end - start
# Длина пути через границу (обходного)
cross_len = N - linear_len
# Мы храним запросы в формате:
# (Длина обходного пути, левая граница билетов, правая граница билетов, кол-во людей)
# Левая граница включительно, правая не включительно (Python style range)
# Билет i (1-based) -> индекс i-1
requests.append((cross_len, start - 1, end - 1, c))
# Сортируем запросы: сначала выгоднее перекидывать те, у которых обходной путь короче
# (они меньше нагружают систему при перевороте)
requests.sort(key=lambda x: x[0])
# 1. Строим базовую нагрузку (все идут линейно)
# Используем разностный массив для быстрого построения
diff = [0] * (N + 1)
for _, l, r, c in requests:
diff[l] += c
diff[r] -= c
base_load = [0] * N
curr = 0
for i in range(N):
curr += diff[i]
base_load[i] = curr
# 2. Дерево отрезков для отслеживания максимума
# Размер дерева должен быть степенью двойки
size = 1
while size < N:
size *= 2
tree = [0] * (2 * size)
lazy = [0] * (2 * size)
# Построение дерева
def build():
for i in range(N):
tree[size + i] = base_load[i]
for i in range(size - 1, 0, -1):
tree[i] = max(tree[2*i], tree[2*i+1])
build()
def update(l, r, val):
# Итеративное обновление на отрезке [l, r)
l += size
r += size
l0, r0 = l, r
while l < r:
if l & 1:
apply(l, val)
l += 1
if r & 1:
r -= 1
apply(r, val)
l //= 2
r //= 2
# Обновление пути к корню
l, r = l0, r0
while l > 1:
l //= 2
r //= 2 # для r не нужно точное соответствие, просто поднимаемся
# Для корректного обновления родителей нужно пройтись по всем затронутым
# Но в итеративном варианте с lazy проще сделать pull после всего
pass
# Полный пересчет затронутых веток (медленнее, но надежнее для max)
# Оптимизированный вариант:
l = l0
r = r0 - 1
while l > 1:
l //= 2
push_up(l)
while r > 1:
r //= 2
push_up(r)
def apply(idx, val):
tree[idx] += val
lazy[idx] += val
def push_up(idx):
# Значение узла = max(детей) + собственное lazy
# Важно: lazy не спускаем вниз в этой реализации, а учитываем при чтении
# Но для max операции lazy нужно прибавлять к результату детей
val_left = tree[2*idx]
val_right = tree[2*idx+1]
tree[idx] = max(val_left, val_right) + lazy[idx]
# Начальный ответ (без переворотов)
min_max_load = tree[1]
current_global_offset = 0
# 3. Жадный перебор
for _, l, r, c in requests:
# Переворачиваем запрос:
# Вместо пути [l, r) (линейного) используем дополнение.
# Математически: Load_new = Load_old + C (везде) - 2C (на отрезке [l, r))
# Добавляем C глобально (просто в переменную)
current_global_offset += c
# Вычитаем 2C на отрезке [l, r) в дереве
update(l, r, -2 * c)
# Текущий максимум = Максимум в дереве + глобальное смещение
current_max = tree[1] + current_global_offset
if current_max < min_max_load:
min_max_load = current_max
print(min_max_load)
if __name__ == '__main__':
solve()
