Penyuluhan Petani

Batas Waktu	 1 detik
Batas Memori	 32 MB
Pak Agri bekerja sebagai Kepala Bidang Penerangan Pertanian yang berada di bawah Kementrian Pertanian di Negeri Algoria. Salah satu tugas yang diembannya adalah untuk mengadakan penyuluhan kepada para petani di daerah-daerah di seluruh pelosok negeri, misalnya jika ada informasi mengenai bibit unggul yang baru, ancaman hama padi, resiko bencana banjir atau kekeringan, dan sebagainya.

Dalam melaksanakan proses penyuluhan ini, Pak Agri biasanya mengirim petugas penyuluh ke Unit Kelompok Petani (UKP) yang ada di setiap desa. Karena jumlah UKP yang tersebar di seluruh pelosok Negeri Algoria cukup besar, biaya pengiriman petugas bisa melambung tinggi. Untungnya, beberapa UKP menjalin hubungan yang erat satu dengan yang lain, dan selalu mengkomunikasikan informasi apapun yang mereka terima. Artinya, jika satu UKP menjalin hubungan dengan sebuah UKP lain, maka jika salah satu menerima informasi penyuluhan yang baru (baik dari pegawai penyuluh langsung maupun dari UKP lainnya), ia akan membagi informasi tersebut ke UKP yang satunya. Hal ini tentu menguntungkan bagi Pak Agri, karena itu berarti ia dapat menghemat biaya pengiriman petugas penyuluhan, karena bisa jadi tidak semua UKP perlu dikunjungi oleh seorang petugas penyuluhan.

Pak Agri telah mendapatkan informasi yang lengkap mengenai semua hubungan komunikasi antar UKP, serta biaya pengiriman petugas penyuluhan ke setiap UKP. Bantulah Pak Agri untuk menentukan, berapa minimal total biaya pengiriman petugas yang harus dikeluarkan, sedemikian rupa sehingga semua UKP mendapatkan informasi yang diinginkan.

Format Masukan

Baris pertama berisi dua buah bilangan, N dan M. N menyatakan banyaknya UKP sedangkan M menyatakan banyaknya hubungan antar UKP. Setiap UKP diberikan nomor dari 1 hingga N. M baris berikutnya masing-masing berisi sepasang bilangan bulat positif a, b, menyatakan bahwa UKP nomor a dan b saling menjalin hubungan. Perhatikan bahwa a menjalin hubungan dengan b juga berarti bahwa b menjalin hubungan dengan a. Lebih lanjut, hanya salah satu di antara "a b" atau "b a" yang akan diberikan pada input (tidak dua-duanya).

N baris berikutnya berisi biaya pengiriman ke masing-masing UKP (dalam ribuan).

Format Keluaran

Keluaran berupa satu baris berisi bilangan bulat positif yang menyatakan total biaya pengiriman (dalam ribuan) terkecil yang harus dikeluarkan instansi Pak Agri sedemikan rupa sehingga sebuah informasi yang ingin disampaikan pada kegiatan penyuluhan dapat diterima oleh semua UKP (baik melalui pegawai penyuluhan yang dikirimkan oleh Pak Agri, maupun melalui komunikasi antar UKP).

Contoh Masukan

6 4
1 2
2 3
2 4
5 6
50
30
20
30
40
30


Contoh Keluaran

50


Penjelasan

Ada 6 UKP, dan 4 hubungan komunikasi antar UKP: 1 dan 2, 2 dan 3, 2 dan 4 serta 5 dan 6.  Pak Agri dapat mengirim cukup 2 petugas penyuluhan: 1 orang ke UKP 3 (biaya 20 ribu) dan satu orang lagi ke UKP 6 (biaya 30 ribu), sehingga total biaya = 50 ribu. Perhatikan bahwa skema ini sudah cukup untuk menyebarkan informasi ke seluruh UKP, karena UKP 2 akan mendapatkan informasi penyuluhan dari UKP 3, sedangkan UKP 1 dan 4 akan mendapatkan informasi yang sama dari UKP 2, serta UKP 5 mendapatkan informasi penyuluhan dari UKP 6. Tidak ada cara lain yang menghasilkan total biaya lebih kecil dari 50 ribu.

Batasan

1000 < N < 200000

10000 < M < 1000000

1 < biaya pengiriman < 200