Elevi Pentru Elevi Arges - XI/XII | Zboruri

Tocmai ați fost angajat la compania aeriană „Brătianu Airlines”. Știți că există $N$ orașe indexate de la $1$ la $N$ între care compania organizează $M$ trasee de zbor. Se dă fiecare traseu de zbor prin numărul orașului din care decolează, orașul în care aterizează, durata și prețul zborului.
Din cauza unei supraîncărcări a rețelei, cauzată de aglomerația din aeroport, trebuie să găsiți manual o metodă de a găsi zboruri pentru pasageri.

Cerință

Pentru două orașe date, $S$ și $F$, trebuie să aflați:

1. Un drum$^{[1]}$ de la orașul $S$ la orașul $F$ care să aibă durată$^{[2]}$ minimă, dacă există.
2. Dintre toate drumurile de durată minimă de la orașul $S$ la orașul $F$, care este prețul$^{[3]}$ minim al unui astfel de drum, dacă există.

$^{[1]}$ Numim drum de la un oraș $U$ la un oraș $V$ un șir $X_1$, $X_2$, ..., $X_k$, unde $X_1 = U$ și $X_k = V$, iar pentru orice $i$, cu $1 \le i < K$, există un zbor de la $X_i$ la $X_{i + 1}$.

$^{[2]}$ Definim durata unui drum $X_1$, $X_2$, ..., $X_k$ ca fiind suma duratelor zborurilor de la $X_i$ la $X_{i + 1}$, cu $1 \le i < K$.

$^{[3]}$ Definim prețul unui drum $X_1$, $X_2$, ..., $X_k$ ca fiind suma prețurilor zborurilor de la $X_i$ la $X_{i + 1}$, cu $1 \le i < K$.

Date de intrare

Pe prima linie a fișierului de intrare zboruri.in se află cinci numere naturale nenule, în această ordine: $C$, $N$, $M$, $S$, respectiv $F$, unde $C$ reprezintă numărul cerinței care se va rezolva, iar restul au semnificațiile din enunț.

Pe următoarele $M$ linii se află descrierile celor $M$ zboruri, câte un zbor pe linie. Al $i$-lea zbor, cu $1 \le i \le M$, este dat prin patru numere naturale nenule, în această ordine:

• $U_i$ - orașul de decolare;
• $V_i$ - orașul de aterizare;
• $T_i$ - durata zborului;
• $P_i$ - prețul zborului.

Date de ieșire

Fișierul de ieșire zboruri.out va conține pe prima linie:

• Pentru $C = 1$, șirul $X_1$, $X_2$, ..., $X_k$, ce reprezintă un drum de durată minimă de la orașul $S$ la orașul $F$, dacă există. Dacă nu există niciun astfel de drum se va afișa numărul $-1$.
• Pentru $C = 2$, un singur număr natural $P_{min}$, ce reprezintă prețul minim dintre prețurile tuturor drumurilor de durată minimă de la $S$ la $F$, dacă există. Dacă nu există niciun astfel de drum se va afișa numărul $-1$.

Restricții și precizări

• $2 \le N \le 2 \cdot 10^5$
• $2 \le M \le \min(2 \cdot 10^5, N \cdot (N - 1))$
• $1 \le U_i, V_i \le N$, cu $1 \le i \le M$
• $1 \le T_i, P_i \le 10^9$, cu $1 \le i \le M$
• Pentru prima cerință, dacă există mai multe drumuri de durată minimă, se va puncta oricare dintre acestea.
• Se acordă 10 puncte din oficiu.

Exemplul 1

zboruri.in

1 6 8 1 4
1 2 3 3
1 6 1 1
2 3 5 1
2 5 2 2
3 4 3 1
5 4 4 2
6 2 2 1
6 5 4 3

zboruri.out

1 2 5 4

Exemplul 2

zboruri.in

2 6 8 1 4
1 2 3 3
1 6 1 1
2 3 5 1
2 5 2 2
3 4 3 1
5 4 4 2
6 2 2 1
6 5 4 3

zboruri.out

6

Explicație

Zborurile din ambele exemple se pot reprezenta grafic ca în imaginea următoare:

Cercurile reprezintă orașele, cu indicele lor înăuntru, și săgețile reprezintă zborurile, unde este notată cu albastru durata zborului și cu roșu prețul zborului.

Pentru primul exemplu, durata minimă a unui zbor este $9$, iar toate zborurile cu această durată sunt:

• $1$, $6$, $5$, $4$;
• $1$, $6$, $2$, $5$, $4$;
• $1$, $2$, $5$, $4$.

Oricare dintre acestea este considerat corect.

Pentru al doilea exemplu, drumurile de durată minimă de mai sus au prețurile:

• $1 + 3 + 2 = 6$;
• $1 + 1 + 2 + 2 = 6$;
• $3 + 2 + 2 = 7$.

Astfel prețul minim al unui drum de durată minimă este $6$.