#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long
#define all(x) x.begin(),x.end()
struct edge{
int a,b,c,d;
};
const int mxn=205;
multiset<pair<int,int>> adj[mxn];
ll dp[mxn];
ll dijkstra(int st,int en){
memset(dp,0x3f3f3f3f,sizeof(dp));
dp[st]=0;
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
pq.push({0,st});
while(!pq.empty()){
ll dist;
int v;
dist=pq.top().f;
v=pq.top().s;
pq.pop();
if(dist!=dp[v]) continue;
for(auto u:adj[v]){
ll fin=dp[v]+u.s;
if(fin<dp[u.f]){
dp[u.f]=fin;
pq.push({dp[u.f],u.f});
}
}
}
return dp[en];
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n,m;
cin>>n>>m;
vector<edge> E(m);
for(int i=0;i<m;i++){
int a,b,c,d;
cin>>a>>b>>c>>d;
E[i]={a,b,c,d};
adj[a].insert({b,c});
}
ll ans=1e18;
for(auto v:E){
int a,b,c,d;
a=v.a,b=v.b,c=v.c,d=v.d;
adj[a].erase(adj[a].find({b,c}));
adj[b].insert({a,c});
ans=min(ans,d+dijkstra(1,n)+dijkstra(n,1));
adj[a].insert({b,c});
adj[b].erase(adj[b].find({a,c}));
}
cout<<ans;
return 0;
}
