package Ġpast Ċ Ċ import Ġutilities . debug Log Ċ import Ġjava . util .* Ċ Ċ fun Ġmain ( args : ĠArray < String >) Ġ{ ĊĠĠĠ Ġval Ġsc Ġ= ĠScanner ( System .` in `) ĊĠĠĠ Ġval Ġn Ġ= Ġsc . nextInt () ĊĠĠĠ Ġval Ġx Ġ= Ġsc . next Long () ĊĠĠĠ Ġval Ġabc Ġ= Ġ( 0 Ġuntil Ġn Ġ- Ġ 1 ). map Ġ{ ĠTrip le ( sc . next (). toInt (), Ġsc . next (). toInt (), Ġsc . next (). toInt ()) Ġ} ĊĠĠĠ Ġprintln ( problem 0 0 8 h ( n , Ġx , Ġabc )) Ċ } Ċ Ċ fun Ġproblem 0 0 8 h ( n : ĠInt , Ġx : ĠLong , Ġabc : ĠList < Triple < Int , ĠInt , ĠInt >> ): ĠString Ġ{ ĊĠĠĠ Ġval Ġroutes Ġ= ĠArray ( n Ġ+ Ġ 1 ) Ġ{ Ġmutable ListOf < Pair < Int , ĠInt >>() Ġ} ĊĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn Ġ- Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġ( a , Ġb , Ġc ) Ġ= Ġabc [ i ] ĊĠĠĠĠĠĠĠ Ġroutes [ a Ġ- Ġ 1 ]. add ( b Ġ- Ġ 1 Ġto Ġc ) ĊĠĠĠĠĠĠĠ Ġroutes [ b Ġ- Ġ 1 ]. add ( a Ġ- Ġ 1 Ġto Ġc ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġval Ġans Ġ= ĠLong Array ( n ) Ġ{ Ġ 0 Ġ} ĊĠĠĠ Ġval Ġq Ġ= ĠPriority Queue < Pair < Int , ĠInt >> Ġ{ Ġx : ĠPair < Int , ĠInt >, Ġy : ĠPair < Int , ĠInt > Ġ-> ĊĠĠĠĠĠĠĠ Ġx . second . compareTo ( y . second ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfor Ġ( city Ġin Ġ 0 Ġuntil Ġn ) Ġ{ ĊĠĠĠĠĠĠĠ Ġq . clear () ĊĠĠĠĠĠĠĠ Ġval Ġcosts Ġ= ĠLong Array ( n ) Ġ{ ĠLong . MAX _ VALUE Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġdone List Ġ= ĠBoolean Array ( n ) Ġ{ Ġfalse Ġ} ĊĠĠĠĠĠĠĠ Ġfor Ġ( j Ġin Ġ 0 Ġuntil Ġroutes [ city ]. size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġ( route , Ġcost ) Ġ= Ġroutes [ city ][ j ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġq . add ( route Ġto Ġcost ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcosts [ route ] Ġ= ĠMath . min ( costs [ route ], Ġcost . to Long ()) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġwhile Ġ( q . isNotEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġ( route , Ġ_) Ġ= Ġq . poll () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( done List [ route ]) Ġcontinue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdone List [ route ] Ġ= Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġroutes [ route ]. size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġ( next Route , Ġnext Cost ) Ġ= Ġroutes [ route ][ i ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġcost Ġ= Ġcosts [ route ] Ġ+ Ġnext Cost ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( cost Ġ< Ġcosts [ next Route ]) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcosts [ next Route ] Ġ= Ġcost ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq . add ( next Route Ġto Ġcost . toInt ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġcosts . size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( i Ġ== Ġcity ) Ġcontinue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( costs [ i ] Ġ== Ġx ) Ġreturn Ġ" Yes " ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġans [ city ] Ġ= Ġif Ġ( costs [ city ] Ġ== ĠLong . MAX _ VALUE ) Ġ- 1 Ġelse Ġcosts [ city ] ĊĠĠĠ Ġ} ĊĠĠĠ Ġreturn Ġ" No " Ċ }