eolymp
bolt
Try our new interface for solving problems
Məsələlər

Граффити

Граффити

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Задан взвешенный неориентированный граф с n вершинами и m ребрами. Граф не содержит петель и может быть нарисован на плоскости. Нурлашко восстановил граф на плоскости и построил следующий граф: грани (области) на плоскости стали вершинами, а ребрами между ними стали ребра, общие к этим граням. Например, если 2 грани имели общее ребро в исходном графе, то следует добавить ребро между гранями в новом графе. Теперь Нурлашко хочет найти минимальное остовное дерево нового графа. Минимальное остовное дерево - это связное дерево с n вершинами с минимальной суммой ребер в дереве.

Giriş verilənləri

Первая строка содержит 2 целых числа n и m (3n1000000, 0m200000). Каждая из следующих m строк содержит 3 целых числа: u, v, c (1u, vn, uv, -10^6c10^6), где u и v - вершины, c - вес соединяющего их ребра.

Çıxış verilənləri

Выведите одно целое число - вес минимального остовного дерева.

Nümunə

Giriş verilənləri #1
3 3
1 2 1
2 3 1
1 3 1
Çıxış verilənləri #1
1
Mənbə 2019 Fall KBTU OPEN, Задача G