Algorithmen Übungen WS 2008/2009

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, a ≠ b, 1 ≤ c ≤ 10⁶); 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.