Algorithmen Übungen WS 2008/2009

Bei dieser Aufgabe versetzen wir uns zurück ins Mittelalter, als es noch Ritter gab. Eine der wesentlichen Tätigkeiten eines Ritters ist es, an Turnieren teilzunehmen. Bei einem typischen Turnier müssen die Ritter in Disziplinen wie Schwertkampf, Bogenschießen und verschiedenen Reitkämpfen gegeneinander antreten. Natürlich braucht jeder Ritter für die Reitkämpfe sein eigenes Pferd.

Leider braucht ein Ritter oft mehrere Tage, um von seiner Burg zu dem Ort zu gelangen, an dem das Turnier stattfinden soll. Und Pferde können ziemlich störrisch sein; so kann es vorkommen, dass das Pferd nach einer bestimmten Entfernung stehenbleibt und erst am nächsten Tag wieder weitergeht. Da der Ritter nicht mitten auf dem Land übernachten will, plant er die Reiseroute zum Turnier so, dass die maximale Tagesstrecke, die er mit seinem Pferd zurücklegt, möglichst gering ist. Daher ist eine lange Reiseroute, die viele Tage mit kurzen Tagesstrecken beinhaltet, besser als eine kurze Reiseroute mit einer langen Tagesstrecke.

Schreiben Sie ein Programm, dass eine optimale Reiseroute für einen Ritter findet, d. h. eine Reiseroute, bei der die maximale Tagesstrecke der Reiseroute minimal ist.

Eingabe

Die erste Zeile der Eingabe enthält die Anzahl n an möglichen Übernachtungsorten (2 ≤ n ≤ 10000). Die Übernachtungsorte werden mit Zahlen zwischen 1 und n benannt, wobei die Burg des Ritters mit 1 benannt wird, und der Ort des Turniers mit n.

Die zweite Zeile der Eingabe enthält die Anzahl an möglichen Tagesstrecken m (n-1 ≤ m ≤ 200000). Die folgenden m Zeilen enthalten jeweils drei natürliche Zahlen a b c, die die Tagesstrecken beschreiben, wobei a und b zwei unterschiedliche Orte bezeichnen, zwischen denen der Ritter reisen kann (sowohl von a nach b als auch andersherum), und c gibt die Distanz an (1 ≤ c ≤ 10⁹).

Ausgabe

Die Ausgabe soll die Distanz der maximalen Tagesstrecke sein, die der Ritter zurücklegen muss, um den Turnierort zu erreichen. Sie können annehmen, dass immer mindestens eine Verbindung von der Ritterburg zum Turnierort existiert.

Beispiel

Eingabe:
6
7
1 2 5
2 3 1
3 6 1
1 4 4
4 6 4
1 5 5
6 5 7
Ausgabe:
4

Die optimale Verbindung ist hier 1 -> 4 -> 6