doo

#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>

const int ROWNIK = 360*3600;


using namespace std;

class ladowanie;

class polaczenie
{
public:
    int cel;
    int cena;
    int dlugosc;
    polaczenie(int _cel, int _cena, int _dlugosc) { cel = _cel; cena = _cena; dlugosc = _dlugosc; };
    polaczenie() { cel=0; cena=0; dlugosc=0; };
    ladowanie lec( const ladowanie &skad );
};




class miasto
{
public:
    int wspolrzedna;
    vector < polaczenie > polaczenia ;
    miasto(){wspolrzedna=0;}
    miasto(int _wspolrzedna) {wspolrzedna= _wspolrzedna;};
    vector<ladowanie> podrozuj( const ladowanie &start );
};





class ladowanie //etap wycieczki
{
public:
    int indeks_miasta; //indeks miasta
    int nakrycie; // topologiczne nad S^1 ;)
    int koszt; // jak daleko w bajtotalarach od miasta 1.
    int wspolrzedna;
    ladowanie () { indeks_miasta=0; nakrycie=0; koszt =0;wspolrzedna=0;};
    ladowanie (int m, int wsp) { indeks_miasta=m; nakrycie=0; koszt =0;wspolrzedna=wsp;};
};

int przesuniecie(miasto &a, miasto &b , int k)
{
    int roznica = (ROWNIK+ k*b.wspolrzedna - k*a.wspolrzedna) % ROWNIK;
    return roznica*k;
};


ladowanie polaczenie::lec( const ladowanie &skad )
{
    ladowanie cel_lotu = ladowanie(this->cel, skad.wspolrzedna+this->dlugosc);
    cel_lotu.koszt = skad.koszt + this->cena;
    cel_lotu.nakrycie = skad.nakrycie;
    if (cel_lotu.wspolrzedna<0)
    {
        cel_lotu.nakrycie--;
        cel_lotu.wspolrzedna+=ROWNIK;
    }else if(cel_lotu.wspolrzedna>=ROWNIK)
    {
        cel_lotu.nakrycie++;
        cel_lotu.wspolrzedna-=ROWNIK;
    }
    return cel_lotu;
}

 struct porownaj_koszt
 {
     bool operator() (const ladowanie &a,const ladowanie &b)const
            { return (a.koszt > b.koszt); } //kolejka piorytetowa trzyma największy, wiec odwracamy relacje
 };

 struct porownaj_indeks
 {
     bool operator () (const ladowanie &a, const ladowanie &b)const
     {   return (a.indeks_miasta< b.indeks_miasta);  }
};

vector<ladowanie> miasto::podrozuj( const ladowanie &start )
{
    int n=this->polaczenia.size();
    vector<ladowanie> wyloty(n);
    for (int i=0;i<n;i++)
    {
        wyloty [i] = this->polaczenia[i].lec(start);
    }
    return wyloty;
}

int main()
{
    int n,m;
    scanf("%d %d",&n,&m);



    vector <miasto> miasta(n+1);

    for (int i=1;i<=n;i++)
    {
        int pozycja;
        scanf("%d",&pozycja);
        miasta[i]=miasto(pozycja);
    }
    for (int i=0;i<m;i++)
    {
        int a,b,x,k;
        scanf("%d %d %d %d", &a,&b,&x,&k);
        int przes = przesuniecie(miasta[a],miasta[b],k);
        miasta[a].polaczenia.push_back(polaczenie(b,x, przes));
        miasta[b].polaczenia.push_back(polaczenie(a,x, -przes));
    }


    priority_queue<ladowanie, vector<ladowanie>, porownaj_koszt> kolejka;
    kolejka.push(ladowanie(1,miasta[1].wspolrzedna));

    priority_queue<int, vector<int>, greater<int> >taniosc; // ;)

    set<ladowanie,porownaj_indeks> odwiedzone; //miasta (x) kakrycie zminimalizowane

    while (!kolejka.empty())
    {
        ladowanie L = kolejka.top();
        kolejka.pop();

        set<ladowanie,porownaj_indeks>::iterator it;
        it = odwiedzone.find(L);

        if ((it->indeks_miasta == L.indeks_miasta)&&(it!=odwiedzone.end()) && (odwiedzone.size()>0) ) // w tym mieście już lądowaliśmy
        {
            if (it->nakrycie!=L.nakrycie)//znaleźliśmy cykl, zamykający się w tym mieście!
            {//wrzucamy propozycję na stosik i nie podróżujemy dalej z tego lądowania.
                taniosc.push(L.koszt+it->koszt);
                odwiedzone.insert(L);
            };// else to samo nakrycie-> to samo lądowanie, ale z konstrukcji alg.D gorsze. Olewamy
        }
        else
        { //nie ma miasta na liscie.
            odwiedzone.insert(L);
            vector<ladowanie> nowe_loty = miasta[L.indeks_miasta].podrozuj(L);
            //Dodajemy wszystko, co stad wylatuje
            for (int i=0;i<nowe_loty.size(); i++)
            {
                kolejka.push(nowe_loty[i]);
            }
        }

    }//Dijkstra skonczył;

    if (taniosc.empty())
    {
        printf("-1\n");
    }
    else
    {
        printf("%d\n",taniosc.top());
    }



    return 0;
}