又到暑假了，住在城市A的Car想和朋友一起  去城市B旅游。她知道每個(gè)城市都有四個(gè)飛機(jī)場，分別位于一個(gè)矩形的四個(gè)頂點(diǎn)上，同一個(gè)城市中兩個(gè)機(jī)場之間有一  條筆直的高速鐵路，第I個(gè)城市中高速鐵路了的單位里程價(jià)格為Ti，任意兩個(gè)不同城市的機(jī)場之間均有航線，所有航線單位里程的價(jià)格均為t。
那么Car應(yīng)如何安排到城市B的路線才能盡可能的節(jié)省花費(fèi)呢?她發(fā)現(xiàn)這并不是一個(gè)簡單的問題，于是她來向你請教。
找出一條從城市A到B的旅游路線，出發(fā)和到達(dá)城市中的機(jī)場可以任意選取，要求總的花費(fèi)最少。

第一行有四個(gè)正整數(shù)S，t，A，B。 
S表示城市的個(gè)數(shù)，t表示飛機(jī)單位里程的價(jià)格，A，B分別為城市A，B的序號(hào)，(1< =A，B< =S)。 

接下來有S行，其中第I行均有7個(gè)正整數(shù)xi1，yi1，xi2，yi2，xi3，yi3，Ti，這當(dāng)中的(xi1，yi1)，(xi2，yi2)，(xi3，yi3)分別是第I個(gè)城市中任意三個(gè)機(jī)場的坐標(biāo)，T  I為第I個(gè)城市高速鐵路單位里程的價(jià)格。 

數(shù)據(jù)規(guī)模和約定
0< S< =100，

零基礎(chǔ)同學(xué)可以先學(xué)習(xí)視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，點(diǎn)擊這里了解課程詳情

藍(lán)橋杯 圖論