Problem E
Esports on my Mind

Nú er loksins úrslitaleikurinn í Striker-Count að byrja. Allir meðlimir KFFÍ eru mættir og flatbakan er komin í hús. Atli ákvað að koma að horfa á leikinn þrátt fyrir að hafa ekki mikinn áhuga á Striker-Count. Atli fær því Berg til að útskýra hvernig leikurinn virkar.

Í Striker-Count keppa tvö fimm manna lið. Annað liðið er kallað bláa liðið og hitt liðið er kallað gula liðið. Í hálfleik skipta svo liðin um lit. Liðið sem vinnur leikinn fær eitt stig, og það lið sem fyrr fær tvö stig vinnur mótið. Leikirnir eru spilaðir á mismunandi borðum. Á hverju borði eru tvær sprengistæður sem bláa liðið á að verja frá gula liðinu. Gula liðið vill koma fyrir sprengju á stæðunum. Sprengjan tekur $40$ sekúndur að springa og á meðan þarf gula liðið að verja sprengjuna svo bláa liðið aftengi hana ekki. Ef sprengjan springur, þá vinnur alltaf gula liðið umferðina. Annars, ef allir í öðru liðinu deyja tapar það lið umferðinni. Í síðasta lagi tapar gula liðið ef það nær ekki að koma fyrir sprengjunni eða drepa bláa liðið á tveimur mínútum. Fyrra liðið til að vinna $16$ umferðir vinnur leikinn og hálfleikur er eftir $15$ umferðir. Ef lokastaðan er $15:15$ þarf að fara í bráðabana. Atli tekur fljótt eftir að í byrjun á hverri umferð hlaupa leikmenn af stað og koma sér fyrir á sömu stöðunum. Bergur útskýrir fyrir honum að leikmenn þurfa að flýta sér á suma staðina á borðinu í upphafi umferðar því það tekur liðin, um það bil, jafn langan tíma að komast þangað. Bergur kallar þessa staði vígvelli. Atli tekur þó eftir það tekur ekki alltaf sama tíma að komast á staðina. Bergur segir honum að stundum byrja leikmennirnir umferðina lengra frá stöðunum sem þeir vilja komast á, sumir leikmenn eru fljótari á milli staða en aðrir og leikmenn ferðast mishratt eftir því á hvaða vopnum þeir halda. Atla finnst því réttara að skoða mögulega vígvelli, staðir sem gætu orðið vígvellir. Hverju borði má lýsa sem stefndu, vigtuðu neti. Ef það er leggur frá hnút $u$ til $v$ með vigt $w$ er hægt að fara frá hnút $u$ til $v$ á að meðaltali $w$ tíma. Sérhver leggur $e$ hefur einnig skekkju $\sigma _ e$. Ef vigt $e$ er $w$ tekur minnst $w - \sigma _ e$ tíma að ferðast eftir leggnum og mest $w + \sigma _ e$. Atli vill skilgreina hnút sem mögulegan vígvöll ef til er $-\sigma _ e \leq d_ e \leq \sigma _ e$ fyrir hvern legg $e$ þannig að ef vigt allra leggja $e$, gefin með $w_ e$, er skipt út fyrir $w_ e + d_ e$ þá verður sá hnútur vígvöllur. Hnútur er vígvöllur ef bæði liðin eru jafn lengi að komast þangað ef þau fara bæði stystu mögulegu leið. Hvaða hnútar eru mögulegir vígvellir í upphafi umferðar?

Mynd af netinu í sýniinntaki $3$

Inntak

Fyrsta lína inntaksins inniheldur tvær heiltölur $n$ og $m$, með $1 \leq n, m \leq 10^5$. Hér táknar $n$ fjölda hnúta og $m$ fjölda leggja. Næsta lína inntaksins inniheldur tvær heiltölur $b$ og $g$, með $1 \leq b, g \leq n$. Talan $b$ gefur upphafsstaðsetningu bláa liðsins og $g$ gefur upphafsstaðsetningu gula liðsins. Gefið er að $b \neq g$. Næstu $m$ línur innihalda fjórar heiltölur $u, v, w, \sigma $, með $1 \leq u, v \leq n$, $1 \leq \sigma \leq w \leq 10^9$. Þær tákna legg frá hnút $u$ til $v$ með vigt $w$ og skekkju $\sigma $. Gefið er að netið inniheldur engar snörur og sérhvert $(u, v)$ par í inntakinu kemur mest fyrir einu sinni.

Úttak

Úttakið skal innihalda þá hnúta sem eru mögulegir vígvellir, í vaxandi röð, á einni línu. Ef það er enginn mögulegur vígvöllur skal prenta ‘Thessi leikur verdur sennilega leidinlegur’.

5 6
1 5
1 2 5 2
1 3 1 1
1 4 2 1
3 4 1 1
5 2 2 1
5 4 5 1

2

4 4
1 4
1 2 10 1
1 3 5 1
4 2 5 1
4 3 10 1

Thessi leikur verdur sennilega leidinlegur

13 38
2 10
1 2 2 1
1 11 7 2
1 5 4 1
2 1 2 1
2 3 3 1
3 2 3 1
3 7 2 2
3 4 6 1
4 3 6 1
4 8 7 2
5 1 4 1
5 2 1 1
5 6 4 2
6 5 4 2
6 7 1 1
6 9 8 3
6 12 10 4
7 3 2 2
7 8 8 2
7 9 10 3
8 4 7 2
8 7 8 2
8 10 13 2
9 6 8 3
9 7 10 3
9 10 3 1
9 12 4 2
10 8 16 5
10 9 3 1
10 12 4 2
11 1 7 2
11 12 4 1
11 13 1 1
12 6 10 4
12 9 4 2
12 10 4 2
12 11 4 1
13 11 1 1

6 7 8 11 13