Pis yollar — Eolymp

Giriş

Birinci sətrdə şəhərlərin sayı $n$ ( $1 \leq n \leq 100$ 1 \leq n \leq 100), yolların sayı $m$ ( $1 \leq m \leq 1 0^{4}$ 1 \leq m \leq 10^4), başlanğıc şəhər $s$ və son şəhər $t$ ( $1 \leq s, t \leq n$ 1 \leq s, t \leq n) verilir. İkinci sətrdə $money$ ( $0 \leq money \leq 1 0^{6}$ 0 \leq \text{money} \leq 10^6) və $maxtime$ ( $0 \leq maxtime \leq 1 0^{6}$ 0 \leq \text{maxtime} \leq 10^6) verilir.

Növbəti $m$ sətrin hər birində bir yol təsvir olunur: $u_{i}$ u_i $v_{i}$ v_i $c_{i}$ c_i $t_{i}$ t_i $h_{i}$ h_i. Burada $u_{i}$ u_i — $i$ -ci yolun başlanğıc şəhəri, $v_{i}$ v_i — son şəhəri, $c_{i}$ c_i — yol özəldirsə $1$ (əks halda $0$ ), $t_{i}$ t_i — yolda hərəkət vaxtı və $h_{i}$ h_i — avtomobilin altının tələb olunan hündürlüyü ( $1 \leq u_{i}, v_{i} \leq n$ 1 \leq u_i, v_i \leq n, $0 \leq t_{i} \leq 1 0^{4}$ 0 \leq t_i \leq 10^4, $0 \leq h_{i} \leq 1 0^{6}$ 0 \leq h_i \leq 10^6). Bütün yollar biristiqamətlidir. Girişdəki bütün ədədlər tamdır.

Çıxış

Əgər qoyulan məhdudiyyətlər daxilində $s$ -dən $t$ -yə çatmaq mümkün deyilsə, -1 çıxış verin. Əks halda, birinci sətirdə tələb olunan minimal avtomobil altı hündürlüyünü; ikinci sətirdə seçilmiş marşrutda olan yolların sayını; üçüncü sətirdə isə istifadə olunan yolların (1-dən $m$ -ə qədər, giriş ardıcıllığında) nömrələrini səyahət ardıcıllığı ilə çıxış verin.

Nümunələr

Nümunə 1

Loading