Təsadüfi Gəzinti DAG-da#3378
Siz təpə və kənardan ibarət istiqamətli acıqlı qraf araşdırırsınız. Qrafda dövrələr yoxdur. Siz təpədən başlayırsınız. Hər bir təpədə siz çıxış kənarlarından birini təsadüfi olaraq seçirsiniz, seçmə ehtimalı kənarın çəkisinə proporsionaldır.
Siz çıxış kənarı olmayan bir təpəyə çatana qədər araşdırmanı davam etdirirsiniz. Araşdırmanızın uzunluğu keçdiyiniz kənarların sayıdır. Əlavə olaraq, təpədən gəzintiyə başlamamışdan əvvəl, siz qrafdan bir kənarı silməyi seçə bilərsiniz (və ya heç bir kənarı silməyə də bilərsiniz). Kənarı nəzərə almamaq üçün ən yaxşı seçimi (və ya heç birini silməməyi) etməklə, gəzintinizin mümkün olan ən böyük gözlənilən uzunluğunu tapın.
Girişdə bir neçə test halı verilir. Hər test halı iki tam ədəd olan bir sətrlə başlayır: , 2 \leq N \leq 10000, və , 1 \leq M \leq 100000 — qrafdakı təpələrin və kənarların sayı. Növbəti sətrin hər birində üç tam ədəd , və (1 \leq w \leq 1000) verilir, bu isə təpəsindən təpəsinə çəkisi olan istiqamətli kənar olduğunu bildirir (təpələr -dan N-1-ə qədər nömrələnir). Giriş N = M = 0 olan sətrlə tamamlanır.
Hər test halı üçün, gəzintinizin mümkün olan ən böyük gözlənilən uzunluğunu verən bir sətr yazın. Cavabınız 10^{-6} dəqiqlikdə (mütləq və ya nisbi) uyğun olarsa, düzgün hesab olunacaq.
Nümunə 1