Sizdə tıxac var

Siz yeni avtomobillər üçün ağıllı yol hərəkətinin idarəetmə sisteminə cavabdehsiniz. Məqsədiniz, şəhərin quruluşu və digər avtomobillərin hərəkəti haqqında məlumatdan istifadə edərək, səhər pik saatlarında yataq rayonlarından şəhər mərkəzinə gedən sürücülərin tıxaclarını qarşısını almaqdır.

Təəssüf ki, sürücülər eqoist olduqları üçün, siz onlardan bunu istəsəniz belə, heç vaxt şəhər mərkəzinə gedən mümkün olan ən qısa yoldan başqa bir yolla getməyəcəklər. Siz onlara yalnız bir neçə ən qısa yoldan hansını seçmələrini tövsiyə edə bilərsiniz.

Şəhər, müəyyən edilmiş vaxtda keçilə bilən iki tərəfli yollarla birləşdirilmiş kəsişmələrdən ibarətdir. Bütün sürücülər hərəkətə kəsişmələrdən (mümkün ki, müxtəlif) başlayır və şəhər mərkəzi olaraq təyin edilmiş 1 nömrəli kəsişmədə bitirirlər. Əgər iki sürücü eyni anda eyni yolda eyni istiqamətdə hərəkətə başlasa, tıxac yaranacaq və sizin məqsədiniz uğursuz olacaq. Lakin sürücülər eyni anda eyni kəsişmədən keçə və ya eyni yolda fərqli vaxtlarda hərəkət edə bilərlər.

Bütün sürücülər eyni anda hərəkətə başlayarsa və heç biri qeyri-optimal yolla getməzsə, tıxac olmadan şəhər mərkəzinə çata biləcək maksimum sürücü sayını müəyyən edin.

C.1 şəkilində avtomobillər başlanğıc yerlərində təsvir edilmişdir. Bir sürücü artıq mərkəzdədir və 4 nömrəli kəsişmədə olan avtomobillərdən biri 3 nömrəli kəsişmədən keçərək nöqtəli xətt boyunca hərəkət edə bilər, digəri isə 2 nömrəli kəsişmədən keçərək nöqtəli xətt boyunca hərəkət edə bilər, lakin qalan iki avtomobil tıxac olmadan mərkəzə çata bilməyəcək. Beləliklə, bu testin cavabı 3 olacaq.

Giriş verilənləri

Birinci sətir üç ədəd $n,m$ və $c$ ehtiva edir, burada $n(1\le n\le 25000)$ - kəsişmələrin sayı, $m(0\le m\le 50000)$ - şəhərdəki yolların sayı və $c(0\le c\le 1000)$ - sürücülərin sayıdır. Növbəti $m$ sətirin hər biri $x_i,y_i$ və $t_i$ ədədlərini ehtiva edir, burada $x_i$ və $y_i(1\le x_i,y_i\le n)$ - təsvir edilən yolun birləşdirdiyi müxtəlif kəsişmələrin nömrələri və $t_i(1\le t_i\le 10000)$ - sürücünün yolun başlanğıcından sonuna qədər hər iki istiqamətdə keçməsi üçün sərf etməli olduğu vaxtdır. Hər kəsişmədən mərkəzə çatmağın mümkün olduğu təmin edilir. Sonuncu sətir maşınların yerləşdiyi başlanğıc kəsişmələrini təsvir edən c ədəd ehtiva edir.

Çıxış verilənləri

Tıxac olmadan şəhər mərkəzinə çata biləcək maksimum sürücü sayını çıxarın.

Nümunələr