#include <bits/stdc++.h>
#define V vector
#define L(i,j,k) for(int i=(j);i<=(k);i++)
#define R(i,j,k) for(int i=(j);i>=(k);i--)
#define all(x) x.begin(),x.end()
#define sz(a) ((int)a.size())
#define pb push_back
using namespace std;
typedef long long ll;
//Si tengo un nodo, tengo dos opciones, hacer la arista i "única"
//Hacer el color C único en el nodo v
const int MAXN=2000+5;
const ll INF=1e18;
struct Edge{
int a,b,c,p;
};
ll sum[MAXN][MAXN],c[MAXN],p[MAXN];
V<pair<int,int>> adj[MAXN];
ll dist[MAXN][MAXN];
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;cin>>n>>m;
L(i,1,m){
int u,v;cin>>u>>v;
cin>>c[i]>>p[i];
adj[u].pb({v,i});
adj[v].pb({u,i});
sum[u][c[i]]+=p[i];
sum[v][c[i]]+=p[i];
}
L(i,1,n){
L(j,0,m)dist[i][j]=INF;
}
dist[1][0]=0;
using iii=pair<ll,pair<ll,ll>>;
priority_queue<iii,vector<iii>,greater<iii>>pq;
pq.push({0,{1,0}});
while(sz(pq)){
auto [d,d2]=pq.top();pq.pop();
auto [u,e]=d2;
if(dist[u][e]!=d)continue;
for(auto [v,i]:adj[u]){if(i==e)continue;
ll &ret=dist[v][0],eq=sum[u][c[i]]-(e!=0&&c[i]==c[e]?p[e]:0);
if(ret>d+(eq-p[i])){
ret=d+(eq-p[i]);
pq.push({ret,{v,0}});
}
ll &ret2=dist[v][i];
if(ret2>d+p[i]){
ret2=d+p[i];
pq.push({ret2,{v,i}});
}
}
}
ll ans=INF;
L(i,0,m){
ans=min(ans,dist[n][i]);
}
if(ans==INF)cout<<-1<<endl;
else cout<<ans<<endl;
}
