#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
const int N=100050;
const int M=3*N;
vector<array<int,3>> E[N];
vector<pair<int,ll>> G[M];
void AddEdge(int u,int v,ll w){
assert(w>=0);
G[u].pb({v,w});
}
const ll inf=1e18;
ll dist[M];
int par[M];
int main(){
int n,m;
scanf("%i %i",&n,&m);
for(int i=1;i<=m;i++){
int u,v,c,w;
scanf("%i %i %i %i",&u,&v,&c,&w);
E[u].pb({v,c,w});
E[v].pb({u,c,w});
}
map<pair<int,int>,int> nodes;
int tsz=n;
for(int i=1;i<=n;i++){
map<int,int> cnt;
for(auto e:E[i]){
cnt[e[1]]++;
}
for(auto e:E[i]){
if(cnt[e[1]]>1){
nodes[{i,e[0]}]=++tsz;
AddEdge(tsz,i,0);
}
}
}
for(int i=1;i<=n;i++){
map<int,int> cnt;
map<int,ll> sum;
map<int,vector<pair<int,int>>> mx;
for(auto e:E[i]){
cnt[e[1]]++;
sum[e[1]]+=e[2];
mx[e[1]].pb({e[2],e[0]});
}
for(auto& it:mx)sort(it.second.begin(),it.second.end());
for(auto e:E[i]){
if(cnt[e[1]]==1){
AddEdge(i,e[0],0);
if(nodes.find({e[0],e[1]})!=nodes.end()){
AddEdge(i,nodes[{e[0],e[1]}],e[2]);
}
}else{
int from=nodes[{i,e[0]}];
int mxNode=mx[e[1]][0].second;
int mxW=mx[e[1]][0].first;
if(e[0]==mxNode){
mxNode=mx[e[1]][1].second;
mxW=mx[e[1]][1].first;
}
AddEdge(from,mxNode,sum[e[1]]-mxW-e[2]);
int to=nodes.count({e[0],i})?nodes[{e[0],i}]:e[0];
AddEdge(i,to,e[2]);
AddEdge(i,e[0],sum[e[1]]-e[2]);
}
}
}
for(int i=1;i<=tsz;i++)dist[i]=inf;
dist[1]=0;
priority_queue<pair<ll,int>> pq;
pq.push({0,1});
while(pq.size()){
int u=pq.top().second;
ll d=-pq.top().first;
pq.pop();
if(d!=dist[u])continue;
for(auto e:G[u]){
int v;ll w;tie(v,w)=e;
if(dist[v]>dist[u]+w){
dist[v]=dist[u]+w;
par[v]=u;
pq.push({-dist[v],v});
}
}
}
if(dist[n]==inf)printf("-1\n");
else{
printf("%lld\n",dist[n]);
/*stack<int> stk;
int u=n;
while(u!=1){
stk.push(u);
u=par[u];
}
stk.push(1);
while(stk.size()){
printf("%i ",stk.top());
stk.pop();
}*/
}
return 0;
}
