XI Wiosenny Turniej w Programowaniu Zespołowym Politechnika Poznańska, 26 V 2007

Opis

Bolek jest wiochmenem. Każdego roku, odbywa on wycieczkę rowerową pomiędzy dwoma wioskami. Jest wiele różnych tras, które może on obrać, lecz jest pewna maksymalna długość trasy, której nie chce przekroczyć. Mając dane informacje o wioskach, drogach oraz ich długościach, Bolek chciałby mieć listę różnych tras pomiędzy dwoma wybranymi wioskami, których długość nie przekracza jego możliwości, tak aby spokojnie wybrać sobie, którąś z nich. Twoim zadaniem jest napisanie programu, który wypisze listę tych tras od najkrótszej do najdłuższej.

Przyjmujemy następujące założenia:

• Maksymalnie jedna droga łączy każdą parę wiosek, jest ona dwukierunkowa i jej długość jest niezerowa.
• Nie ma dróg, które by biegły z danej wioski do tej samej wioski. To przecież bez sensu!
• Bolka interesuje tylko wycieczka w jednym kierunku. Nie interesuje go powrót.
• Bolek nie chce odwiedzać żadnej wioski dwukrotnie podczas swojej podróży.

Specyfikacja wejścia

W pierwszej linii wejścia znajduje się liczba testów D. Dalej następują opisy testów. Pierwsza linia każdego testu składa się z dwóch liczb całkowitych V i R (2 ≤ V ≤ 20, 0 ≤ R ≤ 40). V oznacza liczbę wiosek, a R liczbę dróg pomiędzy nimi. W każdym z kolejnych R wierszy znajduje się opis i-tej drogi w postaci trzech liczb Ci, Di, Oi. Pierwsze dwie oznaczają numery wiosek połączonych drogą, a Oi oznacza odległość między nimi. Wioski numerowane są od 1 do V, a 1 ≤ Oi ≤ 10000. W kolejnej linii znajdują się 2 różne liczby X i Y, oznaczające, odpowienio, numer wioski początkowej oraz numer wioski docelowej. W ostatniej linii występuje jedna liczba całkowita M (1 ≤ M ≤ 10000), oznaczająca maksymalną długość trasy, która Bolek jest gotów pokonać.

Specyfikacja wyjścia

Dla każdego testu z wejścia, w oddzielnych liniach wypisz trasy spełniające wymagania Bolka poprzedzone długością danej trasy i dwukropkiem. Trasy powinny być wypisane w kolejności od najkrótszych do najdłuższych. W przypadku tras o takiej samej długości wypisz je w kolejności leksykograficznej. Wyniki kolejnych testów oddziel pustymi liniami.

W przypadku, gdy żadna trasa nie spełnia ograniczeń Bolka, wypisz słowo NIE

Przykład

3
4 5
1 2 2
2 3 2
1 4 1
3 4 4
1 3 3
1 3
4
4 5
1 2 2
2 3 2
1 3 3
3 4 4
1 4 1
1 4
10
5 7
1 2 2
2 4 2
1 4 5
3 4 3
2 5 3
3 5 2
2 3 1
1 3
8

3: 1 3 
4: 1 2 3 

1: 1 4 
7: 1 3 4 
8: 1 2 3 4 

3: 1 2 3 
7: 1 2 4 3 
7: 1 2 5 3 
8: 1 4 2 3 
8: 1 4 3