#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1<<17;
vector<pair<int,pair<int,int>>> Vec[N], Raw[N];
vector<pair<int,int>> nei[N];
int seen[N], Min[N];
void Add(int u, int v, int d, int flg = 0){
// cout<<u<<" ";
// cout<<(flg ? '-' : '<');
// cout<<"---> "<<v<<" "<<" "<<d<<'\n';
nei[u].push_back({v, d});
}
void dfs(int u){
seen[u] = 1;
sort(begin(Raw[u]), end(Raw[u]));
for (int i=0;i<Raw[u].size();i++){
auto [a1, b1] = Raw[u][i];
int j = i, Sm = b1.second;
while (j + 1 < Raw[u].size() and Raw[u][j+1].first == a1)
j++, Sm += Raw[u][j].second.second;
for (int k=i;k<=j;k++){
auto [a, b] = Raw[u][k];
Add(u, b.first, min(b.second, Sm - b.second));
if (seen[b.first] == 0)
dfs(b.first);
}
if (j == i + 1){
auto [a2, b2] = Raw[u][i+1];
Add(b1.first, b2.first, b1.second);
Add(b2.first, b1.first, b2.second);
}
i = j;
}
}
void dfs2(int u){
seen[u] = 2;
sort(begin(Vec[u]), end(Vec[u]));
for (int i=0, id = 0;i<Raw[u].size();i++){
auto [a1, b1] = Raw[u][i];
int j = i, Sm = b1.first;
while (j + 1 < Raw[u].size() and Raw[u][j+1].first == a1)
j++, Sm += Raw[u][j].second.second;
for (int k=i;k<=j;k++){
auto [a, b] = Raw[u][k];
if (seen[b.first] != 2)
dfs2(b.first);
while (id < Vec[u].size() and Vec[u][id].first == a and Vec[u][id].second.first == b.first)
Add(u, Vec[u][id].second.second, min(b.second, Sm - b.second), 1), id++;
}
i = j;
}
}
void dijkstra(int u){
for (int i=2;i<N;i++)
Min[i] = 1e9;
set<pair<int,int>> st = {{0, 1}};
while (st.size() > 0){
auto [mn, u] = *begin(st);
st.erase(begin(st));
for (auto [i, w] : nei[u]){
if (Min[u] + w < Min[i]){
st.erase({Min[i], i});
Min[i] = Min[u] + w;
st.insert({Min[i], i});
}
}
}
}
int main(){
int n, m;
cin>>n>>m;
for (int i=1, a, b, c, d;i<=m;i++){
cin>>a>>b>>c>>d;
Raw[a].push_back({c, {b, d}});
Raw[b].push_back({c, {a, d}});
}
dfs(1);
// dfs2(1);
// return 0;
dijkstra(1);
if (Min[n] == 1e9)
Min[n] = -1;
cout<<Min[n]<<'\n';
}
