#include <bits/stdc++.h>
#define N 205
#define M 50005
#define int long long
using namespace std;
struct edge{
int u,v,c,d,i;
};
vector<edge> edges(M);
vector<edge> adj[N];
int dp[N][N],dp2[N][N],dp3[N][N];
vector<pair<int,int>> dijkstra(int st,int nd){
vector<int> dist(N,1e18);
vector<pair<int,int>> par(N);
dist[st] = 0;
priority_queue<pair<int,int>> q;
q.push({0,st});
while(q.size()){
auto tp = q.top();
q.pop();
tp.first *=-1;
if(tp.second == nd){
vector<pair<int,int>> path;
int now = nd;
path.push_back({nd,0});
while(now != st){
path.push_back(par[now]);
now = par[now].first;
}
reverse(path.begin(),path.end());
return path;
}
if(tp.first != dist[tp.second])continue;
for(auto u:adj[tp.second]){
if(dist[u.v] > dist[u.u] + u.c){
dist[u.v] = dist[u.u] + u.c;
par[u.v] = {u.u,u.i};
q.push({-dist[u.v],u.v});
}
}
}
return {};
}
void solve(){
int n,m;
cin >> n >> m;
for(int i=1;i<=m;i++){
int u,v,c,d;
cin >> u >> v >> c >> d;
adj[u].push_back({u,v,c,d,i});
edges[i] = {u,v,c,d};
}
auto path1 = dijkstra(1,n);
auto path2 = dijkstra(n,1);
map<int,int> mp1,mp2;
for(int i = 0;i<(int)path1.size()-1;i++){
mp1[path1[i].second] = i+1;
}
for(int i = 0;i<(int)path2.size()-1;i++){
mp2[path2[i].second] = i+1;
}
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
dp[i][j] = dp2[i][j] = dp3[i][j] = 1e18;
}
dp[i][i] = dp2[i][i] = dp3[i][i] = 0;
}
for(int i=1;i<=m;i++){
dp[edges[i].u][edges[i].v] = min(dp[edges[i].u][edges[i].v],edges[i].c);
if(!mp1[i]){
dp2[edges[i].u][edges[i].v] = min(dp2[edges[i].u][edges[i].v],edges[i].c);
}
if(!mp2[i]){
dp3[edges[i].u][edges[i].v] = min(dp3[edges[i].u][edges[i].v],edges[i].c);
}
}
for(int x=1;x<=n;x++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dp[i][j] = min(dp[i][j],dp[i][x] + dp[x][j]);
dp2[i][j] = min(dp2[i][j],dp2[i][x] + dp2[x][j]);
dp3[i][j] = min(dp3[i][j],dp3[i][x] + dp3[x][j]);
}
}
}
int ans = 1e18;
ans = min(ans,dp[1][n] + dp[n][1]);
for(int i=1;i<=m;i++){
int now = edges[i].d;
if(mp1[i]){
int mini = 1e18;
for(int l=0;l<=mp1[i]-1;l++){
for(int r = mp1[i];r<path1.size();r++){
int x = path1[l].first;
int y = path1[r].first;
mini = min(mini, dp[1][x] + dp2[x][y] + dp[y][n]);
}
}
now += mini;
}
else{
now += min(dp[1][n],dp[1][edges[i].v] + edges[i].c + dp[edges[i].u][n]);
}
if(mp2[i]){
int mini = 1e18;
for(int l=0;l<=mp2[i]-1;l++){
for(int r = mp2[i];r<path2.size();r++){
int x = path2[l].first;
int y = path2[r].first;
mini = min(mini, dp[n][x] + dp3[x][y] + dp[y][1]);
}
}
now += mini;
}
else{
now += min(dp[n][1],dp[n][edges[i].v] + edges[i].c + dp[edges[i].u][1]);
}
ans = min(ans,now);
}
cout << (ans < 1e18?ans:-1);
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef Local
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t=1;
//cin>>t;
while(t--){
solve();
}
#ifdef Local
cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
#endif
}
