#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,int>> G[M];
void AddEdge(int u,int v,int w){
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 col:cnt){
if(col.second==2){
nodes[{i,col.first}]=++tsz;
AddEdge(tsz,i,0);
}
}
}
for(int i=1;i<=n;i++){
map<int,int> cnt;
map<int,ll> sum;
for(auto e:E[i]){
cnt[e[1]]++;
sum[e[1]]+=e[2];
}
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 if(cnt[e[1]]==2){
int n2=nodes[{i,e[1]}];
AddEdge(n2,e[0],0);
if(nodes.find({e[0],e[1]})!=nodes.end()){
AddEdge(n2,nodes[{e[0],e[1]}],e[2]);
}
AddEdge(i,e[0],sum[e[1]]-e[2]);
if(nodes.find({e[0],e[1]})!=nodes.end()){
AddEdge(i,nodes[{e[0],e[1]}],e[2]);
}else{
AddEdge(i,e[0],e[2]);
}
}else{
AddEdge(i,e[0],sum[e[1]]-e[2]);
if(nodes.find({e[0],e[1]})!=nodes.end()){
AddEdge(i,nodes[{e[0],e[1]}],e[2]);
}else{
AddEdge(i,e[0],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,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("%i\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;
}
