Условие

---

ГРУПА B, ЗАДАЧА B. ПРИКЛЮЧЕНИЕ
---
Аня и приятелите й имат малко свободно време и решават да тръгнат на приключение с влак. Те са набелязали M града, които биха искали да посетят, тръгвайки от град 1 и завършвайки в град M, но не ги интересува поредността на останалите градове, нито дали ще посетят всичките. Те, разбира се, тръгват добре подготвени, така че знаят и цената на билетите за влаковете между градовете. 

Обаче градчетата имат една особеност - гарата, на която влаковете пристигат е различна от тази, от която тръгват. Така че Аня и компания имат още едно препятствие за преодоляване - трябва да стигнат от точка 1 до точка N, за да се качат на следващия влак. Но понеже са с тежки чанти, предпочитат това да стане за възможно най-малко време, т.е. преминавайки по възможно най-малко улици (улиците в един град са с еднаква дължина). 

Аня се е подготвила с карта на БДЖ мрежата и карти на отделните градове - списък на всички Ni кръстовища в град i (1 <= i <= M) и връзките между тях. Сега я интересува през кои градове трябва да минат и за всеки град - през кои кръстовища, така че да платят най-малко за билети и да вървят възможно най-малко. Във всяко градче тя и приятелите й започват от кръстовище 1 и завършват в кръстовище Ni.

Важно е да се отбележи, че влаковете се движат само в една посока и успешното достигане до крайната точка винаги е възможно. 

Вход
На първия ред от стандартния вход се четат цели числа M и К - броят на градовете и броят на връзките между тях. Следват К реда, задаващи, че влакът от град X до град Y е на цена T. Следват M на брой блока във формат: Ni Ki  - брой кръстовища и брой връзки между тях, следвани от Ki реда, задаващи, че от кръстовище Vi до кръстовище Ui има улица. Нашите приятели вървят пеш, така че могат да се движат и в двете посоки.

Изход
На първия ред от стандартния изход се очаква едно цяло число - цената на билетите за влаковете. След това са изредени S числа - градовете, през които ще преминат. На всеки от следващите S реда се извежда пътят на движение през съответния град. Ако има няколко маршрута с една цена или разстояние, то се приема който и да е от тях.

Ограничения
0 < M ≤ 500
0 ≤ Ni ≤ 100
0 < T ≤ 100

Примерен вход
5 6
1 2 7
3 2 5
4 5 1
1 3 1
4 3 1
2 5 5
5 7
1 2
2 3
3 1
2 4
3 4
4 5
2 5
3 2
2 1
2 3
4 4
1 2
1 3
3 4
2 4
1 0
8 11
1 2
1 3
2 3
2 6
3 4
3 5
4 6
4 7
6 7
6 8
7 8

Примерен изход
11
1 3 2 5
1 2 5
1 3 4
1 2 3
1 2 6 8