#include <bits/stdc++.h>
using namespace std;
using namespace chrono;
using ll = long long;
ll inf = 1e18;
ll infmic = 1e9;
struct ura
{
int x,y,culoare,pret;
};
ll fall(ll x,ll y)
{
return infmic * x + y;
}
vector<ura>muchii;
int n,m;
unordered_map<ll,int>cul,cost;
unordered_set<int>culori[100005];
vector<ll>d[100005];
vector<vector<pair<pair<int,int>,ll>>>g[100005];
unordered_map<ll,int>idkmap;
unordered_map<ll,ll>sumcost;
void putedge(int x,int y)
{
//cout << x << ' ' << y << endl;
//int c = cul[{x,y}];
//int pret = cost[{x,y}];
int c = cul[fall(x,y)];
int pret = cost[fall(x,y)];
///(x,0) -> (y,0)
ll cost1 = pret;
//ll cost2 = sumcost[{x,c}] - cost1;
ll cost2 = sumcost[fall(x,c)] - cost1;
ll act_cost = min(cost1,cost2);
g[x][0].push_back({{y,0},act_cost});
//cout << "1" << endl;
///(x,0) -> (y,c)
//g[x][0].push_back({{y,idkmap[{y,c}]},0});
g[x][0].push_back({{y,idkmap[fall(y,c)]},0});
//cout << "2" << endl;
///(x,c) -> (y,0)
//act_cost = sumcost[{x,c}] - cost1;
act_cost = sumcost[fall(x,c)] - cost1;
//g[x][idkmap[{x,c}]].push_back({{y,0},act_cost});
g[x][idkmap[fall(x,c)]].push_back({{y,0},act_cost});
//cout << "3" << endl;
}
signed main()
{
auto primul_moment = high_resolution_clock::now();
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int x,y,culoare,pret;
cin >> x >> y >> culoare >> pret;
//sumcost[{x,culoare}] += pret;
//sumcost[{y,culoare}] += pret;
sumcost[fall(x,culoare)] += pret;
sumcost[fall(y,culoare)] += pret;
ura aux;
aux.x = x;
aux.y = y;
aux.culoare = culoare;
aux.pret = pret;
muchii.push_back(aux);
//cul[{x,y}] = cul[{y,x}] = culoare;
//cost[{x,y}] = cost[{y,x}] = pret;
cul[fall(x,y)] = cul[fall(y,x)] = culoare;
cost[fall(x,y)] = cost[fall(y,x)] = pret;
culori[x].insert(culoare);
culori[y].insert(culoare);
}
for (int i = 1; i <= n; i++)
{
d[i].resize(culori[i].size() + 1);
for (int j = 0; j <= culori[i].size(); j++)
d[i][j] = inf;
g[i].resize(culori[i].size() + 1);
int jjj = 0;
for (auto it : culori[i])
{
jjj++;
//idkmap[{i,it}] = jjj;
idkmap[fall(i,it)] = jjj;
}
}
auto al_doilea_moment = high_resolution_clock::now();
auto cat_a_durat = duration_cast<milliseconds>(al_doilea_moment - primul_moment);
for (auto it : muchii)
{
putedge(it.x,it.y);
putedge(it.y,it.x);
}
//if (cat_a_durat.count() >= 1500)
// assert(false);
priority_queue<pair<ll,pair<int,int>>>pq;
pq.push({0,{1,0}});
while (!pq.empty())
{
pair<int,int>nod = pq.top().second;
ll timp = -pq.top().first;
pq.pop();
if (d[nod.first][nod.second] == inf)
{
d[nod.first][nod.second] = timp;
if (nod.first == n and nod.second == 0)
break;
for (auto vecin : g[nod.first][nod.second])
{
pair<ll,pair<int,int>>de_bagat;
de_bagat.first = -(timp + vecin.second);
de_bagat.second = vecin.first;
pq.push(de_bagat);
}
}
}
if (d[n][0] == inf)
cout << -1;
else
cout << d[n][0];
return 0;
}
/**
Stari: {nod,-1}, {nod,cul}, [nod,cul]
le definesc prin pereche (nod,-1 sau ceva intre 1 si m sau ceva intre 1 si 2m)
pentru nod, pot avea (nod,-1), (nod,c din culori[nod]) sau (nod, m + c din culori[nod])
Tranzitii:
(nod,-1) -> (vecin,-1) cost = min(toate muchiile adiacente cu nod de culoarea cul[{nod,vecin}] mai putin fix muchia {nod,vecin}, cost[{nod,vecin}])
(nod,-1) -> (vecin, cul[{nod,vecin}]) de cost 0
(nod,c) -> (vecin,-1) de cost toate muchiile adiacente cu nod de culoarea c mai putin fix muchia {nod,vecin}, conditie: cul[{nod,vecin}] = c
initial (1,-1) = 0
raspunsul este (n,-1)
**/
/**
graful asta are n + 2m noduri cel mult
(nod,c) pot sa pp ca are doar muchii de culoarea c
atunci numarul de muchii este 2m + 2m + 2m = 6m muchii
pe care dau un dijksta finut, iese N = n + 2m si M = 6m, iese MlogM + N
**/
/**
cum tin graful?
pai am o matrice de stari
la o linie am asa:
(nod,0) reprezinta (nod,-1)
(nod,1),(nod,2),...,(nod,k[nod]) reprezinta culorile din nod
**/
