Fukushima
Национална Олимпиада по Информатика 2011, Кръг 3
Time Limit: 2s, Memory Limit: 256MiB
Скорошните събития в Япония бяха отразени дори в не толкова новинарското списанието Космополитан, а така съответно достигнаха и до Ели. Тя се загрижи значително за случващото се и проведе допълнително проучване на проблемите там. Най-големият от тях е, че почти всички ядрени експерти на страната вече са облъчени с близка до максималната разрешена радиация за година (която, малко след инцидента, беше увеличена четири пъти).

Наскоро в авариралата централа бяха изпратени специални роботи, които да измерят радиацията. В зависимост от нейното ниво различни специалисти ще трябва да влязат в централата за да предотвратят допълнителни избухвания. Дейността на някои от тях зависи от дейността на други – например атомните физици не могат да спрат реакторите преди те да бъдат охладени достатъчно от военните. Те пък от своя страна не могат да свършат това преди ремонтните работници да възстановят електроенергията до централата, която беше прекъсната в следствие на цунамито. Някои от хората може да се нуждаят от повече от една група специалисти да свършат своята дейност – примерно военните може да се нуждаят и от биоинженери, които да приготвят специални химикали, временно неутрализиращи радиацията за да влязат. Ако пък роботите измерят сравнително ниска радиация, военните ще могат да влязат и без въпросните химикали, тоест те няма да се нуждаят от биоинженерите.

За по-нагледно Ели си представя картината като насочен претеглен граф, в който върховете са различни специалисти, а теглата по ребрата са минималната радиация, при която първите специалисти биха се нуждаели работата на вторите да е вече свършена преди да могат да влязат. Тоест ако имаме насочено ребро от A към B с тегло C, то специалистите от тип А ще се нуждаят от специалистите от тип B само ако радиацията в реактора е C или по-висока.

Понякога е невъзможно да се предотврати избухването на централаната. Например ако физиците се нуждаят от военните, военните от биоинженерите, а биоинженерите от физиците, то се получава затворен цикъл и никой не може да свърши своята работа.

Ели решава да извърши своята роля в спасяването на света, като открие каква е максималната радиация, при която операцията ще е възможна.
Вход
На първия ред от стандартния вход ще бъдат зададени две цели числа N и M, задаващи броя специалисти и броя връзки между тях. Всеки от следващите M реда ще съдържа три цели числа: Ai, Bi и Ci, указващи, че специалистите от тип Ai биха се нуждали от специалистите от тип Bi ако радиацията е Ci или по-висока. Няма да има повече от едно ребро от Ai към Bi. Също така няма да има ребро от Аi към Аi.
Изход
На първия ред на стандартния изход изведете едно цяло число, указващо максималното ниво на радиация, при което все още има начин да се изготви план за влизането на специалистите, при който светът да бъде спасен от още една ядрена криза. Ако това е възможно при произволно големи нива на радиация, изпечатайте -1. На втория ред изведете N числа – номерата на специалистите в реда, в който трябва да влизат в централата, за да стане това. Ако има повече от един възможен начин да стане това, изведете лексикографски най-малкия.
Ограничения
  • 1 ≤ N ≤ 100,000
  • 0 ≤ M ≤ 200,000
  • 1 ≤ Ai, BiN
  • 1 ≤ Ci ≤ 1,000,000
Примерен Вход Примерен Изход
7 13 2 1 6 6 4 64 1 6 42 4 3 17 4 7 12 3 7 20 7 6 19 6 7 11 7 5 35 3 5 4 3 2 13 7 2 55 2 5 1 18 1 5 2 3 7 4 6
4 3 2 1 6 4 2 6 3 1 6 -1 1 2 3 4
В първия пример, при ниво на радиацията 18 все още е възможно да се спаси света, като специалистите трябва да влизат в реда, в който е указано в примерния изход. Възможно е да има и други последовалности, при които това е възможно, но от вас се иска да изведете лексикографски най-малката.
Мрън!