有一位使者要游歷各國(guó)，他每到一個(gè)國(guó)家，都能  學(xué)到一種文化，但他不愿意學(xué)習(xí)任何一種文化超過(guò)一次（即如果他學(xué)習(xí)了某種文化，則他就不能到達(dá)其他有這種文化的國(guó)家）。不同的國(guó)家可能有相同的文化。不同  文化的國(guó)家對(duì)其他文化的看法不同，有些文化會(huì)排斥外來(lái)文化（即如果他學(xué)習(xí)了某種文化，則他不能到達(dá)排斥這種文化的其他國(guó)家）。
現(xiàn)給定各個(gè)國(guó)家間的地理關(guān)系，各個(gè)國(guó)家的文化，每種文化對(duì)其他文化的看法，以及這位使者游歷的起點(diǎn)和終點(diǎn)（在起點(diǎn)和終點(diǎn)也會(huì)學(xué)習(xí)當(dāng)?shù)氐奈幕?，?guó)家間的道路距離，試求從起點(diǎn)到終點(diǎn)最少需走多少路。

輸入輸出樣例說(shuō)明
由于到國(guó)家2必須要經(jīng)過(guò)國(guó)家1，而國(guó)家2的文明卻排斥國(guó)家1的文明，所以不可能到達(dá)國(guó)家2。

第一行為五個(gè)整數(shù)N，K，M，S，T，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開，依次代表國(guó)家個(gè)數(shù)（國(guó)家編號(hào)為1到N），文化種數(shù)（文化編號(hào)為1到K），道路的條數(shù)，以及起點(diǎn)和終點(diǎn)的編號(hào)（保證S不等于T）； 
第二行為N個(gè)整數(shù)，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開，其中第i個(gè)數(shù)Ci，表示國(guó)家i的文化為Ci。 
接下來(lái)的K行，每行K個(gè)整數(shù)，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開，記第i行的第j個(gè)數(shù)為aij，aij=  1表示文化i排斥外來(lái)文化j（i等于j時(shí)表示排斥相同文化的外來(lái)人），aij=  0表示不排斥（注意i排斥j并不保證j一定也排斥i）。 

接下來(lái)的M行，每行三個(gè)整數(shù)u，v，d，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開，表示國(guó)家u與國(guó)家v有一條距離為d的可雙向通行的道路（保證u不等于v，兩個(gè)國(guó)家之間可能有多條道路）。 

數(shù)據(jù)規(guī)模和約定
對(duì)于100%的數(shù)據(jù)，有2≤N≤100，1≤K≤100，1≤M≤  N^2，1≤ki≤K，1≤u,  v≤N，1≤d≤1000，S≠T，1  ≤S,  T≤N。

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

藍(lán)橋杯 搜索