POLSKI SPOJ

Spacery po górach

Jasio bardzo lubi spacerować. Postanowił więc skorzystać z wakacji i wyjechać w góry by po nich spacerować.

Pierwszego dnia Jasiu osiągnął wiele szczytów i zauważył, że bardzo lubi obserwować wyższe góry, które już przebył podczas aktualnego spaceru, stojąc na górze niższej niż te które obserwuje. Wymyślił więc, że na następny dzień przygotuje sobie plan, żeby przejść z każdej góry na każdą inną jak najkrótszą drogą, oraz móc obejrzeć jak najwięcej wyższych gór które już przebył. Gdy wrócił do hotelu zabrał się za planowanie, lecz z powodu dużej ilości gór i braku talentu matematycznego, pogubił się w tym. Przypomniał sobie wtedy, że ma przyjaciela-programistę, lubiącego takie łamigłówki.

Jesteś przyjacielem Jasia. Pomóż mu i znajdź odpowiedź na dany problem:

Istnieje N gór oraz M dróg między górami (drogi mogą prowadzić od tej samej góry do tej samej, oraz może istnieć kilka dróg między parami gór). Drogi są dwukierunkowe, oraz mają określone długości.

Góry mają wysokości od 1 do N. Każda góra ma inną wysokość.

Znajdź najkrótsze trasy między wszystkimi parami gór, takie by X było jak największe oraz wypisz wartość X.

Y jest to ilość wszystkich inwersji występujących w sekwencji wysokości gór na trasie.

X jest to suma wszystkich Y dla każdej trasy*.

*Zobacz wyjaśnienie do przykładu żeby lepiej zrozumieć.

Wejście

N (1 <= N <= 200) - Liczba wierzchołków

M (1 <= M <= 500) - Liczba krawędzi

Następne M linii zawiera a_i b_i v_i co oznacza, że istnieje droga od góry o wysokości a_i do góry o wysokości b_i o długości v_{i (vi < 1001)}.

Wyjście

Jedna liczba X - odpowiedź na podany problem.

Przykład

Wejście:
4 4

1 2 4

2 3 4

3 4 4

4 1 4

Wyjście:
12

Wyjaśnienie dla przykładu:

Oto najlepsze drogi między wszystkimi parami gór:

1 -> 2

1 -> 4

1 -> 4 -> 3 (1 inwersja)

2 -> 1 (1 inwersja)

2 -> 3

2 -> 1 -> 4 (1 inwersja)

3 -> 2 (1 inwersja)

3 -> 2 -> 1 (3 inwersje)

3 -> 4

4 -> 1 (1 inwersja)

4 -> 3 (1 inwersja)

4 -> 3 -> 2 (3 inwersje)