#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;
};
int 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=tuple<ll,ll,ll>;
priority_queue<iii,vector<iii>,greater<iii>>pq;
pq.push({0,1,0});
while(sz(pq)){
auto [d,u,e]=pq.top();pq.pop();
for(auto [v,i]:adj[u]){//no pinto la arista
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});
}
}
for(auto [v,i]:adj[u]){//pinto la arista como unica
ll &ret=dist[v][i];
if(ret>d+p[i]){
ret=d+p[i];
pq.push({ret,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;
}
