Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

WEIHNACH - Weihnachtsraub

Kinder glauben nicht an die Wirtschaftskrise. Der wahre Grund für das enttäuschende Nikolausfest ist: Der Nikolaus hat einen Teil der Geschenke auf die Seite geschafft und für sich selbst behalten! Diese Chance wollen die Kinder dem Weihnachtsmann nicht geben. Sie haben beschlossen, den Weihnachtsmann auf dem Weg zur Erde zu überfallen und die Geschenke selbst unter sich aufzuteilen.

Dank Open Streetmap haben sie bereits das himmlische Wegenetz ausspioniert, allerdings ist die genaue Route des Weihnachtsmannes unbekannt. Also wollen sie sich auf die verschiedenen Wege so verteilen, dass der Weihnachtsmann auf jeden Fall an einem ihrer Hinterhalte vorbeikommen muss. Da die Wege unterschiedlich breit sind, werden auf den einzelnen Wegen unterschiedlich viele Kinder für einen Hinterhalt benötigt. Ein weiteres Problem sind die Arbeitszeiten des Weihnachtsmannes: Da er, wie sein Name schon sagt, vorwiegend nachtaktiv ist und Kinder um diese Zeit lieber schlafen, sollen die Hinterhalte so gelegt werden, dass möglichst wenige Kinder benötigt werden. Helfen Sie den Kindern herauszufinden, wieviele Kinder mindestens benötigt werden!

Eingabe

Die erste Zeile der Eingabe enthält die Anzahl n an Wegkreuzungen und die Anzahl m an Wegen (1 ≤ n ≤ 50, 1 ≤ m ≤ 500). Die folgenden m Zeilen enthalten die Beschreibung der Wege. Jeder Weg wird durch drei Zahlen a, b, c beschrieben (1 ≤ a,b ≤ n, ab, 1 ≤ c ≤ 106); das bedeutet, dass ein Weg zwischen den Wegkreuzungen a und b existiert, und mindestens c Kinder für einen Hinterhalt auf diesem Weg benötigt werden. Der Weihnachtsmann startet an Wegkreuzung 1 und will zur Wegkreuzung n.

Ausgabe

Geben Sie die minimale Anzahl an Kindern aus, die benötigt werden, sodass der Weihnachtsmann in jedem Fall an einem der Hinterhalte vorbeikommt.

Beispiel

Eingabe:

5 8
1 2 15
2 3 5
3 4 3
5 4 8 
1 3 8
2 4 9
3 5 20
1 4 11

Ausgabe:

24

In diesem Beispiel ist es optimal, die Straßen zwischen 1 und 3, zwischen 2 und 3, zwischen 3 und 4 sowie zwischen 4 und 5 abzusperren.


Added by:Martin Bader
Date:2008-12-15
Time limit:10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C CSHARP C++ 4.3.2 CPP C99 CLOJURE LISP sbcl LISP clisp D ERL FSHARP FORTRAN GO HASK JAVA JS-RHINO LUA OCAML PERL PERL6 PHP PRLG-swi PYTHON PYTHON3 PY_NBC RUBY SCALA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.