#include <bits/stdc++.h>
#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 205;
struct edge{
int u,v,w,x;
};
vector<edge> edges;
vector<int> adj[N];
int dis[N];
int n,m;
int ans = 1e18;
void dijkstra(int tmp){
int res = 0;
fill(dis,dis+N,1e18);
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> pq;
dis[1] = 0;
pq.push({0,1});
while(!pq.empty()){
auto [ww,u] = pq.top(); pq.pop();
if(ww > dis[u]) continue;
for(auto eid : adj[u]){
if(edges[eid].u==u){
if(dis[edges[eid].v] > dis[u] + edges[eid].w){
dis[edges[eid].v] = dis[u] + edges[eid].w;
pq.push({dis[edges[eid].v],edges[eid].v});
}
}
}
}
res += dis[n];
fill(dis,dis+N,1e18);
dis[n] = 0;
pq.push({0,n});
while(!pq.empty()){
auto [ww,u] = pq.top(); pq.pop();
if(ww > dis[u]) continue;
for(auto eid : adj[u]){
if(edges[eid].u==u){
if(dis[edges[eid].v] > dis[u] + edges[eid].w){
dis[edges[eid].v] = dis[u] + edges[eid].w;
pq.push({dis[edges[eid].v],edges[eid].v});
}
}
}
}
res += dis[1];
ans = min(ans,res+tmp);
}
signed main(){
fastio
cin >> n >> m;
for(int i = 0;i < m;i++){
int u,v,c,d;
cin >> u >> v >> c >> d;
adj[u].push_back(edges.size());
adj[v].push_back(edges.size());
edges.push_back({u,v,c,d});
}
dijkstra(0);
for(auto &e : edges){
swap(e.u,e.v);
dijkstra(e.x);
swap(e.u,e.v);
}
cout << (ans==1e18 ? -1 : ans) << "\n";
}
