棟棟居住在一個繁華的C市中，然而，這個城市的道路大都年久失修。市長準備重新修一些路以方便市民，于是找到了棟棟，希望棟棟能幫助他。

C市中有n個比較重要的地點，市長希望這些地點重點被考慮?，F(xiàn)在可以修一些道路來連接其中的一些地點，每條道路可以連接其中的兩個地點。另外由于C市有一條河從中穿過，也可以在其中的一些地點建設碼頭，所有建了碼頭的地點可以通過河道連接。

棟棟拿到了允許建設的道路的信息，包括每條可以建設的道路的花費，以及哪些地點可以建設碼頭和建設碼頭的花費。

市長希望棟棟給出一個方案，使得任意兩個地點能只通過新修的路或者河道互達，同時花費盡量小。

樣例說明
建設第2、3、4條道路，在地點4、5建設碼頭，總的花費為9。

輸入的第一行包含兩個整數(shù)n,  m，分別表示C市中重要地點的個數(shù)和可以建設的道路條數(shù)。所有地點從1到n依次編號。 
接下來m行，每行三個整數(shù)a,  b,  c，表示可以建設一條從地點a到地點b的道路，花費為c。若c為正，表示建設是花錢的，如果c為負，則表示建設了道路后還可以賺錢（比如建設收費道路）。 
接下來一行，包含n個整數(shù)w_1,  w_2,  …,  w_n。如果w_i為正數(shù)，則表示在地點i建設碼頭的花費，如果w_i為-1，則表示地點i無法建設碼頭。 

輸入保證至少存在一個方法使得任意兩個地點能只通過新修的路或者河道互達。 

數(shù)據(jù)規(guī)模和約定
對于100%的數(shù)據(jù)，1  < =  n  < =  10000，1  < =  m  < =  100000，-1000< =c< =1000，-1< =w_i< =1000，w_i≠0。

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

藍橋杯 圖論