#include <iostream>
#include <cmath>
#include <fstream>
#include <vector>
using namespace std;

ifstream wejscie;
ofstream wyjscie;
int osady,przewoznicy,monety;
int czas,koszt,cel;
int przewoznik[300][5];
int rear,head,temp1,temp3,temp4;
int temp2=1; //zbieranie celow podrozy

typedef struct Opcja
{
    int nr=0; // numer przewoznika
    int skad=0;
    int dokad=0;
    int cena=0;
    int godziny=0;
    int dostep=-1;
    vector <int> droga;
}opcja;
vector <int> sciezka;
void wyzwalacz(opcja tablica[])
{
    for(int i=0;i<przewoznicy;i++)
    {
        if(tablica[i].skad==temp2 && tablica[i].dokad==osady && tablica[i].dostep==-1)
        {
            tablica[i].dostep=0;
            temp3=tablica[i].nr;
            head=temp3;
            tablica[head].droga.push_back(head);
            return;
        }
        if(tablica[i].skad==temp2 && tablica[i].dostep==-1)
        {
            if(temp2==1)
            {
                rear = tablica[i].nr;
            }
            temp2=tablica[i].dokad;
            temp1=tablica[i].nr;
            sciezka.push_back(temp1);
            cout<<"znalazlem cel u przewoznika nr = "<<temp1<<" plyniemy do = "<<temp2<<endl;
            wyzwalacz(tablica);
            temp3 = tablica[i].nr;
            //temp4 = sciezka[sciezka.size()-1];
            //sciezka.pop_back();
            tablica[head].droga.push_back(temp3);
            temp2=tablica[i].dokad;
            //tablica[head].droga.push_back(temp4);
            if(tablica[i].skad==tablica[rear].dokad)
            {
                tablica[head].droga.push_back(rear);
            }
            //return;
        }
    }
}
void wypisanie(opcja tablica[])
{
    int licznik_czasu=0;
    int pomocnik_czasu=0;
    int licznik_monet=0;
    int pomocnik_monet=0;
    for(int j=0;j<przewoznicy;j++)
    {
        if(tablica[j].droga.size()!=0)
        {
            for(int k=tablica[j].droga.size()-1;k>=0;k--)
            {
                pomocnik_monet = tablica[tablica[j].droga[k]].cena;
                licznik_monet+=pomocnik_monet;
                pomocnik_czasu = tablica[tablica[j].droga[k]].godziny;
                licznik_czasu+=pomocnik_czasu;
                cout<<tablica[j].droga[k]<<"->";

            }
            cout<<"\nlicznik monet ="<<licznik_monet;
            cout<<" licznik czasu ="<<licznik_czasu<<endl;
        }
        licznik_czasu=0;
        licznik_monet=0;
    }
}
void pomocnik(opcja tablica[])
{
    int licznik_czasu=0;
    int pomocnik_czasu=0;
    int licznik_monet=0;
    int pomocnik_monet=0;
    int wynik_czasu=-1;
    int wynik_monet=monety+1;
    for(int j=0;j<przewoznicy;j++)
    {
        if(tablica[j].droga.size()!=0)
        {
            for(int k=0;k<tablica[j].droga.size();k++)
            {
                pomocnik_monet = tablica[tablica[j].droga[k]].cena;
                licznik_monet+=pomocnik_monet;
                pomocnik_czasu = tablica[tablica[j].droga[k]].godziny;
                licznik_czasu+=pomocnik_czasu;
                cout<<tablica[j].droga[k]<<"->";
            }
            if(wynik_monet>licznik_monet)
            {
                wynik_czasu=licznik_czasu;
                wynik_monet=licznik_monet;
            }
            cout<<"\nlicznik monet ="<<licznik_monet;
            cout<<" licznik czasu ="<<licznik_czasu<<endl;
        }
        licznik_czasu=0;
        licznik_monet=0;
    }
    cout<<"czas = "<<wynik_czasu<<" monety = "<<wynik_monet<<endl;
}
int main()
{
    wejscie.open("wejscie1.txt");
    wejscie>>osady>>przewoznicy>>monety;
    opcja n[przewoznicy];
    for(int i=0;i<przewoznicy;i++)
    {
        //n[i] = new opcja;
        n[i].nr=i;
        wejscie>>n[i].skad>>n[i].dokad>>n[i].godziny>>n[i].cena;
    }
    wyzwalacz(n);
    pomocnik(n);
    //wypisanie(n);
    //cout<<endl<<czas<<" "<<koszt<<endl;
    return 0;
    }