Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

XIWTPZC - Trasy

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

Wejście

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

Wyjście

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

Dodane przez:Michael Suchacz
Data dodania:2010-04-02
Limit czasu wykonania programu:0.145s-0.491s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU NODEJS OBJC PERL6 SQLITE VB.NET
Pochodzenie:XI Wiosenny Turniej w Programowaniu Zespołowym
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.