Module: Algoritma Dijkstra

Problem

Tulis atur cara yang akan mencari jarak dalam graf berwajaran tidak terarah dengan panjang tepi bukan negatif, daripada bucu yang diberikan kepada setiap bucu lain. Program ini harus pantas untuk graf jarang yang besar.

Input

Baris pertama input mengandungi nombor NUM — bilangan larian berbeza bagi algoritma Dijkstra (pada graf berbeza). Ini diikuti oleh NUM blok, setiap satunya mempunyai struktur berikut.

Baris pertama blok mengandungi dua nombor N dan M dipisahkan oleh ruang — bilangan bucu dan bilangan tepi graf. Ini diikuti oleh M garisan, setiap satu mengandungi tiga integer yang dipisahkan oleh ruang. Dua yang pertama daripadanya, antara 0 hingga N–1 setiap satu, menandakan hujung tepi yang sepadan, yang ketiga — antara 0 hingga 20000 dan menandakan panjang tepi ini. Selanjutnya, dalam baris terakhir blok, satu nombor daripada 0 hingga N–1 — puncak, jarak dari mana anda perlu mencari.

Bilangan graf berbeza dalam satu ujian NUM tidak tidak melebihi 5. Bilangan bucu tidak melebihi 60000, tepi — 200000.

Cetakan

Cetak ke output standard (skrin) NUM baris, setiap satu mengandungi N_i nombor yang dipisahkan oleh ruang — jarak dari puncak permulaan yang ditentukan bagi graf tidak berwajaran ke 0, 1, 2, dsb. bucu (ruang tambahan dibenarkan selepas nombor terakhir). Jika sesetengah bucu tidak boleh dicapai daripada satu permulaan yang ditentukan, cetak nombor 2009000999 dan bukannya jarak (ia dijamin bahawa semua jarak sebenar adalah kurang).

Contoh