تكره الأبقار التمارين الرياضية لكنها تستمتع قليلًا بالهرولة. مسحت المرعى وسردت كل الطرق الممكنة. الطرق «موجهة»، لا تعبر إلا باتجاه واحد. أحيانًا يصل طريقان مختلفان بين نقطتين، أحدهما في اتجاه والآخر بعكسه.
ساعدها على إيجاد أقصر «مسار دائري» للهرولة. يبدأ وينتهي في المكان نفسه. طوله مجموع أطوال الطرق التي تعبرها في الجولة.
تصل الطرق بين نقطتين. لكل نقطة اسم عدد صحيح موجب، بترقيم متتالٍ من 1. المسافات أعداد صحيحة موجبة.
يضمن وجود مسار دائري واحد على الأقل في كل مرعى معطى.
الإدخال
- السطر $1$: $N$ ($1 \le N \le 2000$)، عدد الطرق الموجهة؛ توجد 400 نقطة مختلفة على الأكثر.
- الأسطر $2..N+1$: بداية ونهاية ومسافة (1000 على الأكثر) طريق واحد.
الإخراج
سطر واحد بالمسافة الصحيحة لأقصر دائرة ممكنة.
أمثلة
الإدخال 1
4
3 1 5
1 2 4
2 3 3
1 3 44الإخراج 1
12مؤلفا المسألة: Hal Burch وRuss Cox