Serverin yerləşdirilməsi

Şəhərdə hərbçilər tərəfindən məlumat ötürmək üçün istifadə olunan xüsusi bir kompüter şəbəkəsi var. Tez-tez baş verən raket hücumları nəticəsində ölkənin infrastrukturu ciddi zərər görmüş, şəhər daxilində kompüter şəbəkəsinin fəaliyyəti ilə bağlı problemlər yaranmışdır.

Kompüter şəbəkəsinin ilkin strukturu və şəbəkə düyünləri arasında məlumat ötürmə vaxtı məlumdur. Düyünlər arasında əlaqə varsa, məlumat ən sürətli marşrut üzrə ötürülür.

Şəbəkə zədələndikdən sonra bəzi düyünlər arasında məlumat ötürmə vaxtı artmışdır.

Əsas serveri elə yerləşdirmək lazımdır ki, serverdən ən uzaq (yəni məlumatın ən gec çatdığı) şəbəkə düyünə qədər məlumat ötürmə vaxtı minimal olsun.

Giriş

Birinci sətirdə iki natural ədəd $n$ (1 \leq n \leq 1000) — şəbəkə düyünlərinin sayı və $m$ — bu düyünlər arasında əlaqə kanallarının sayı verilir.

Növbəti $m$ sətirin hər birində üç ədəd verilir: a_i, b_i, c_i (1 \leq a_i, b_i \leq n, 1 \leq i \leq m). Bu, a_i düyünündən b_i düyünə məlumat ötürmə vaxtının c_i millisekund olması deməkdir.

Növbəti sətirdə $k$ (0 \leq k \leq m) — məlumat ötürmə vaxtının artdığı əlaqə kanallarının sayı verilir.

Sonra $k$ sətir gəlir, hər birində üç ədəd: x_i, y_i, z_i (1 \leq x_i, y_i \leq n, 1 \leq i \leq k), burada x_i, y_i — şəbəkə düyünlərinin nömrələri, z_i isə x_i və y_i düyünləri arasında məlumat ötürmə vaxtının z_i millisekund artdığını göstərir.

Çıxış

Əsas serveri elə bir şəbəkə düyünündə yerləşdirmək lazımdır ki, serverdən ən uzaq düyünə qədər olan maksimum məlumat ötürmə vaxtı minimal olsun. Əgər belə düyün bir neçədirsə, onların nömrələrini artan sıra ilə verin.

İzah

Serveri $1$ nöqtəsində yerləşdirmək məsləhətdir. Bu halda ən uzaq düyün $4$-ə məlumat ötürmə vaxtı 25 millisekund olacaq.