Qraf və dövrlər

İstiqamətsiz, çəkili tam qraf verilmişdir və bu qraf n təpədən ibarətdir, burada n təkdir.

k ölçülü dövri massivini, aşağıdakı xüsusiyyətlərə malik olan kənarların [e[1], e[2], ..., e[k]] massivi kimi təyin edək:

• k 1-dən böyükdür.

• 1-dən k-ya qədər hər hansı bir i üçün e[i] kənarı e[i-1] kənarı ilə tam olaraq bir ortaq təpəyə və e[i+1] kənarı ilə tam olaraq bir ortaq təpəyə malikdir, və bu təpələr fərqlidir (qəbul edin ki, e[0] = e[k], e[k+1] = e[1]).

Aydındır ki, dövri massivdəki kənarlar dövr əmələ gətirir.

f(e[1], e[2]) funksiyasını e[1] və e[2] kənarlarını parametr kimi qəbul edən və e[1] və e[2] çəkilərinin maksimumunu qaytaran funksiya kimi təyin edək.

Güman edək ki, dövri massivimiz C = [e[1], e[2], ..., e[k]] var. Dövri massiv qiymətini f(e[i], e[i+1]) cəmi kimi təyin edək, burada i 1-dən k-ya qədərdir (e[k+1] = e[1]).

Qrafın dövri parçalanmasını, birləşməsi qrafın bütün kənarlarını əhatə edən kəsişməyən dövri massivlər dəsti kimi təyin edək. Dövri parçalanmanın qiymətini ona aid massivlərin qiymətlərinin cəmi kimi təyin edək.

Qrafın bir çox mümkün dövri parçalanmaları mövcuddur. Sizin vəzifəniz minimal qiymətə malik dövri parçalanmanı tapmaq və bu qiyməti çıxarmaqdır.

Giriş məlumatları

Birinci sətir qrafda təpələrin sayını göstərən bir tam ədəd n (3 ≤ n ≤ 999, n təkdir) ehtiva edir.

Növbəti n * (n - 1) / 2 sətirin hər biri üç tam ədəd ehtiva edir: u, v və w (1 ≤ u, v ≤ n, u ≠ v, 1 ≤ w ≤ 10^9), bu, u və v təpələri arasında çəkisi w olan kənarın olduğunu göstərir.

Çıxış məlumatları

Bir tam ədəd çıxarın - qrafın minimal mümkün dövri parçalanma qiyməti.

İzah

Kənarları giriş məlumatlarında göründüyü sırayla nömrələyək. e[i] ilə giriş məlumatlarında i-ci olaraq görünən kənarı göstərək.

Birinci nümunədə qrafın yeganə mümkün dövri parçalanması S = {[e[1], e[2], e[3]]}: f(e[1], e[2]) + f(e[2], e[3]) + f(e[3], e[1]) = 1 + 1 + 1 = 3.

İkinci nümunədə qrafın optimal dövri parçalanması: S = {[e[3], e[8], e[9]], [e[2], e[4], e[7], e[10], e[5], e[1], e[6]]}. [e[3], e[8], e[9]] qiyməti 12, [e[2], e[4], e[7], e[10], e[5], e[1], e[6]] qiyməti 23, buna görə parçalanma qiyməti 35.