Çətin test
Andrey Sergeyeviç komanda olimpiadası üçün məsələlərin hazırlanması ilə məşğuldur. Məsələlərdən birinin həlli Deykstra alqoritminə əsaslanır və A.S. bu alqoritm üçün mürəkkəb bir test hazırlamaq istəyir.
Deykstra alqoritmi aşağıdakı kimi işləyir. Qoy G - V zirvələr çoxluğu, E kənar çoxluğu və w : E → R^{+} çəki funksiyası ilə istiqamətli qraf olsun. Qoy bütün zirvələr s zirvəsindən əlçatan olsun. Alqoritm əvvəlcə boş olan U zirvələr çoxluğundan istifadə edir. Hər bir zirvə ya tam ədədlə, ya da +∞ ilə işarələnir. Əvvəlcə bütün zirvələr +∞ ilə işarələnir, s zirvəsi isə sıfırla işarələnir. v zirvəsinin işarəsini d[v] ilə qeyd edək.
Alqoritmin addımı belədir: U-ya daxil olmayan zirvələrdən minimal işarəyə malik olan zirvə seçilir. Qoy bu zirvə u olsun. u zirvəsi U çoxluğuna əlavə olunur və hər bir uv E kənarı relaksasiya olunur. Relaksasiya d[v]-ni min(d[v], d[u] + w(uv)) ilə əvəz edir. Alqoritm bütün zirvələr U-ya əlavə olunanda başa çatır. Əgər v zirvəsinin işarəsi dəyişərsə, relaksasiya aktiv adlanır.
İndi Andrey Sergeyeviç N zirvə və M kənara malik qraf yaratmaq istəyir ki, Deykstra alqoritmi mümkün olan maksimum sayda aktiv relaksasiya etsin. Ona belə bir qraf yaratmağa kömək edin. Müəyyənlikdən qaçmaq üçün qoy hər dəfə U-ya daxil olmayan zirvələrdən minimal işarəyə malik olan yalnız bir zirvə olsun.
Giriş verilənləri
Giriş faylının ilk sətiri iki tam ədəd ehtiva edir: N və M - Andreyin yaratmaq istədiyi qrafda zirvələrin və kənarların sayı (4 ≤ N ≤ 1000, N-1 ≤ M ≤ N^2/5).
Çıxış verilənləri
Çıxış faylına M sətir yazın - qrafın kənarları. Hər bir sətir üç tam ədəd ehtiva etməlidir: kənarın başlanğıcı, sonu və onun çəkisi. Bütün çəkilər qeyri-mənfi olmalı və 10^6-dan çox olmamalıdır. Bütün zirvələr 1 nömrəli zirvədən əlçatan olmalıdır.
Əgər Deykstra alqoritmi s=1 zirvəsindən işə başlayırsa, o, N zirvə və M kənara malik bütün qraflar arasında mümkün olan maksimum sayda aktiv relaksasiya etməlidir. Qraf döngələr və çoxlu kənarlar ehtiva etməməlidir.