Module: Dynamische Programmierung in Graphen

Problem

Heute, in der Burg von Ena, gibt es ein Pier-Festival mit n Bäcker, von denen jeder eine einzigartige Anzahl von 1 bis n hat.
Einige Bäckereien sind durch bilaterale Straßen verbunden, aber wenn die Bäckerei (i) die Bäckerei j erreichen kann, gibt es nur einen Weg zwischen ihnen.

Wann Ein isst Kuchen im i-baby, er bekommt A_I Freude. Und wenn es auf der Straße zwischen einigen Bäckereien mit Zahlen v und u geht, bringt der köstliche Kuchenaromat An C._v,u Freude.

Anne will nicht mehr als einmal in jeder Bäckerei auftauchen (einige Leute kommen überhaupt nicht herein), aber er will das bestmögliche Vergnügen des Festivals.
Es wird in einem der Direktoren beginnen und sich zwischen ihnen nur auf bestehenden Straßen bewegen.

Hilf Ana, das bestmögliche Vergnügen zu bestimmen, das er bekommen kann.

Eingabe:
In der ersten Zeile ist die Anzahl n (1 PO = n PO = 50000) die Anzahl der Bäcker und die Anzahl k die Anzahl der vorhandenen Straßen zwischen Bäckereien.
In der zweiten Zeile sind keine Zahlen A_I (0 Kanal = A_I PER=10000 - Vergnügen von i-cafeteria pies.
Die folgenden Linien sind k, in jeder der 3 Zahlen v, u, C (1: RE= v, u ); v а u; 0 À=C À=10000), was bedeutet, dass es eine Straße zwischen Bäckereien mit Zahlen v und u gibt, und der Aromat auf der Straße bringt Freude an C.

Ausgangsdaten:
Entfernen Sie eine Nummer, so weit wie möglich.

Beispiele:

Eingangsdaten	Ausgangsdaten
Artikel 1 1 1 2 1	3
8 7 1 5 4 6 10 1 2 2 1 2 1 2 3 10 Artikel 2 4 5 1 4 6 2 6 7 2 6 8 3	37.

Beschreibung:
Im ersten Beispiel müssen wir in der ersten Bäckerei (1 Vergnügen), auf der Straße zwischen der 1. und 2. Bäckerei (1 Vergnügen) beginnen und die 2. Bäckerei (1 Vergnügen) besuchen. Gesamtvergnügen - 1+1+1 = 3.
Im zweiten Beispiel muss man in der 5. Bäckerei (10 Appetite), auf der Straße zwischen 5. und 4. Bäckerei (1 Freude), auf der 4. Bäckerei (6 Freuden), auf der Straße zwischen 4. und 2. Bäckerei (1 Freude), auf der 2. Bäckerei (5 Freuden), auf der 2. und 3. Bäckerei (10.) beginnen. Totale Freude - 10+1+6+1+1+5+10+4 = 37.