#include <bits/stdc++.h>
#define int long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define REV(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
using namespace std;
#define MAXN 100005
#define MAXM 200005
int n, m;
struct edge {
int v, c, p;
};
vector<edge> g[MAXN];
map<int, vector<edge>> specG[MAXN];
int dp1[MAXN];
map<int, int> dp2[MAXN];
map<int, bool> visited_dp2[MAXN];
map<int, int> sump[MAXN];
struct club {
int w, u, c;
};
struct CMP {
bool operator() (const club &a, const club &b) const{
return a.w > b.w;
}
};
void solve(){
cin >> n >> m;
FOR(i, 1, m){
int u, v, c, p; cin >> u >> v >> c >> p;
g[u].push_back({v, c, p});
g[v].push_back({u, c, p});
specG[u][c].push_back({v, c, p});
specG[v][c].push_back({u, c, p});
sump[u][c] += p;
sump[v][c] += p;
}
priority_queue<club, vector<club>, CMP> pq;
memset(dp1, 0x3f, sizeof dp1);
dp1[1] = 0;
pq.push({0, 1, 0});
while (pq.size()){
auto [w, u, c] = pq.top();
pq.pop();
if (c == 0){
if (w > dp1[u]) continue;
for (edge &x : g[u]){
auto [V, C, P] = x;
int minVal = 1e15;
// case 1: change this edge's color and go
minVal = min(minVal, w + P);
// case 2: change the color of all other edges that have the same color with this edge
minVal = min(minVal, w + sump[u][C] - P);
if (dp1[V] > minVal){
dp1[V] = minVal;
pq.push({dp1[V], V, 0});
}
// case 3: become a GOD (using dp2)
if (visited_dp2[V][C] == 0){
visited_dp2[V][C] = 1;
dp2[V][C] = 1e15;
}
minVal = w;
if (dp2[V][C] > minVal){
dp2[V][C] = minVal;
pq.push({dp2[V][C], V, C});
}
}
} else {
if (w > dp2[u][c]) continue;
// turn off GOD mode (dp2 -> dp1)
for (edge &x : specG[u][c]){
auto [V, C, P] = x;
int minVal = w + sump[u][c] - P;
if (dp1[V] > minVal){
dp1[V] = minVal;
pq.push({dp1[V], V, 0});
}
}
}
}
if (dp1[n] > 1e15) dp1[n] = -1;
cout << dp1[n];
}
#define task ""
int32_t main(){
if (fopen(task".inp","r")){
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
solve();
return 0;
}
