Streets
Зимни Състезания по Информатика, 2010
Time Limit: 1s, Memory Limit: 64MiB
Елеонора е леко разочарована от това колко много хора успяха да решат гатанката на баба й по време на есенния турнир в Шумен. Да си го кажем направо – тя е на ръба да стане eмо! И, за разлика от повечето си съученици, които най-вероятно биха удавили мъката в алкохол, тя има доста различен начин за справяне с депресията – шопинг!

Ели не мирясва докато не обиколи всяка пазарска улица поне по веднъж. Но ходенето не е малко, а както сигурно знаете – високите токчета не са едни от най-удобните обувки. Затова вие решавате да й помогнете, като по даден граф на пазарските улици намерите маршрут, който минава по всяка една от тях поне по веднъж, и в същото време минимизира изминатото разстояние.
Вход
На първия ред на стандартния вход ще намерите числата N и M – съответно броят кръстовища и улици в графа. На всеки от следващите М реда ще има по 3 цели числа – Fi, Ti, и Pi, отбелязващи еднопосочна улица от кръстовище Fi до кръстовище Ti с дължина Pi.
Изход
На първия ред на стандартния изход изведете едно цяло число цяло число - минималната обща дължина, която трябва да извърви Ели, за да тръгне от кръстовище с номер 1 (където живее тя), да премине всяка улица поне по веднъж, и да се върне отново там. Ако такъв път не съществува, изпечатайте -1. В случай, че има такъв път, на втория ред изпечатайте едно цяло число - през колко кръстовища трябва да мине, за да го постигне, а на третия изпечатайте индексите на въпросните кръстовища, в реда на обхождането им. При наличие на няколко маршрута, които изпълняват условията, изпечатайте кой да е от тях. Графът на улиците е претеглен, насочен, без примки и има най-много едно ребро от едно кръстовище към друго.
Ограничения
  • 1 ≤ N ≤ 500
  • 1 ≤ М ≤ 10,000
  • 1 ≤ Fi, TiN
  • 1 ≤ Pi ≤ 10,000
Примерен Вход Примерен Изход
5 8 1 2 3 1 3 2 2 4 4 3 4 8 3 1 2 3 2 5 4 5 3 5 3 1 42 15 1 2 4 5 3 4 5 3 1 3 2 4 5 3 1
Ели иска да мине през всичките 8 улици поне по веднъж. Забележете, че за да направи това, момичето трябва да мине по някои от улиците по повече от веднъж.
Мрън!