#include <bits/stdc++.h>
using namespace std;
#define int long long
int inf = 1e18;
struct ura
{
int x,y,culoare,pret;
};
vector<ura>muchii;
int n,m;
map<pair<int,int>,int>cul,cost;
set<int>culori[100005];
vector<int>d[100005];
vector<vector<pair<pair<int,int>,int>>>g[100005];
map<pair<int,int>,int>idkmap;
map<pair<int,int>,int>sumcost;
void putedge(int x,int y)
{
//cout << x << ' ' << y << endl;
int c = cul[{x,y}];
int pret = cost[{x,y}];
///(x,0) -> (y,0)
int cost1 = pret;
int cost2 = sumcost[{x,c}] - cost1;
int 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});
//cout << "2" << endl;
///(x,c) -> (y,0)
act_cost = sumcost[{x,c}] - cost1;
g[x][idkmap[{x,c}]].push_back({{y,0},act_cost});
//cout << "3" << endl;
}
signed main()
{
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;
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;
culori[x].insert(culoare);
culori[y].insert(culoare);
}
for (int i = 1; i <= n; i++)
{
d[i].resize(culori[i].size() + 1);
//c[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++;
//c[i][jjj] = it;
idkmap[{i,it}] = jjj;
}
}
for (auto it : muchii)
{
putedge(it.x,it.y);
putedge(it.y,it.x);
}
priority_queue<pair<int,pair<int,int>>>pq;
pq.push({0,{1,0}});
while (!pq.empty())
{
pair<int,int>nod = pq.top().second;
int timp = -pq.top().first;
pq.pop();
if (d[nod.first][nod.second] == inf)
{
d[nod.first][nod.second] = timp;
for (auto vecin : g[nod.first][nod.second])
{
pair<int,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
**/
