#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pi = pair<int,int>;
#define endl "\n"
#define mp make_pair
void setIO(string name = "") {
ios_base::sync_with_stdio(0); cin.tie(0);
if(sz(name)){
freopen((name+".in").c_str(), "r", stdin);
freopen((name+".out").c_str(), "w", stdout);
}
}
const int maxn = 1e5+10;
const int maxm = 2e5+10;
const int INF = 1e18;
int n,m;
struct Edge{
int to, color, price;
};
// vector<Edge> adj[maxn];
// int colorsum[maxn][maxm];
// int dist2[maxn][maxm];
map<int, vector<Edge>> adj[maxn];
map<int, int> colorsum[maxn];
map<int, int> dist2[maxn];
signed main(){
setIO();
cin>>n>>m;
for (int i = 0; i < m; i++){
int a,b,c,d;
cin>>a>>b>>c>>d;
a--; b--;
adj[a][c].pb({b, c, d});
adj[b][c].pb({a, c, d});
colorsum[a][c] += d;
colorsum[b][c] += d;
}
vi dist(n, INF);
dist[0] = 0;
priority_queue<pair<int, pi>, vector<pair<int, pi>>, greater<pair<int, pi>>> pq;
pq.push({0, {0, 0}});
while (!pq.empty()){
auto [d, node] = pq.top();
pq.pop();
auto [cur, color] = node;
if (color){
if (dist2[cur][color] < d) continue;
for (auto e : adj[cur][color]){
int case1 = d+colorsum[cur][e.color]-e.price;
if (case1 < dist[e.to]){
dist[e.to] = case1;
pq.push({case1, {e.to, 0}});
}
}
}
else{
if (dist[cur] < d) continue;
for (auto i : adj[cur]){
for (Edge e: i.second){
int case1 = d + colorsum[cur][e.color] - e.price;
//flip all others
if (case1 < dist[e.to]){
dist[e.to] = case1;
pq.push({case1, {e.to,0 }});
}
int case2 = d + e.price;
//flip this one
if (case2 < dist[e.to]){
dist[e.to] = case2;
pq.push({case2, {e.to, 0}});
}
int case3 = d;
if (!dist2[e.to].count(e.color) || case3 < dist2[e.to][e.color]){
dist2[e.to][e.color] = case3;
pq.push({case3, {e.to, e.color}});
}
}
}
}
}
if (dist[n-1] == INF){
cout<<-1<<endl;
} else {
cout<<dist[n-1]<<endl;
}
}
