Əlaqəli qrafda minimal çəkili gövdəli ağac tapmaq tələb olunur.

Giriş verilənləri

Giriş faylının birinci sətri qrafın təpələrinin və tillərinin sayını ifadə edən iki natural n və m (1 ≤ n ≤ 20000, 0 ≤ m ≤ 100000) ədədlərini ehtiva edir. Növbəti m sətrin hər biri tilləri təsvir edir. i nömrəli til tilin sonluqlarının nömrəsi və onun çəkisini ifadə edən üç natural bi, ei və wi (1 ≤ bi, ei ≤ n, 0 ≤ wi ≤ 100000) ədədləri ilə təsvir olunur.

Qraf əlaqəlidir.

Çıxış verilənləri

Minimal gövdəli ağacın çəkisini ifadə edən yeganə tam ədədi verin.