#include <bits/stdc++.h>
using namespace std;
typedef long long lo;
typedef pair< lo,lo > PII;
#define fi first
#define se second
#define mp make_pair
#define endl "\n"
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)
const lo inf = 1000000000000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 500005;
const lo mod = 1000000007;
int n,m,a[li],k,flag,t,x;
lo cev;
vector<pair<int,pair<int,int>>> v[li];
map<pair<int,int>,int> mpp;
map<pair<int,int>,bool> vis;
inline int in(){
int x;
scanf("%d",&x);
return x;
}
inline void sp(){
priority_queue<pair<int,pair<int,int>>> pq;
pq.push({0,{0,1}});
cev=1000000000000000;
while(pq.size()){
lo co=-pq.top().fi;
int renk=pq.top().se.fi;
int node=pq.top().se.se;
pq.pop();
if(vis[{node,renk}])continue;
vis[{node,renk}]=1;
if(node==n){cev=min(cev,co);continue;}
for(auto go:v[node]){
if(vis[{go.fi,0}]==0)pq.push({-co-mpp[{node,go.se.fi}]+go.se.se,{0,go.fi}});
if(vis[{go.fi,go.se.fi}]==0)pq.push({-co-go.se.se,{go.se.fi,go.fi}});
}
}
if(cev==1000000000000000)cev=-1;
printf("%lld\n",cev);
}
int main(void){
n=in(),m=in();
for(int i=1;i<=m;i++){
int x=in(),y=in(),c=in(),p=in();
v[x].pb({y,{c,p}});
v[y].pb({x,{c,p}});
mpp[{x,c}]+=p;
mpp[{y,c}]+=p;
}
sp();
return 0;
}
