#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<map>
#include<set>
#include<algorithm>
#define ll long long
#define pi pair < ll,ll >
#define mp(a,b) make_pair(a,b)
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 204
#define M 50005
#define INF 1e15
using namespace std;
struct edge{
ll to;
ll cost;
ll reverse_cost;
ll id;
ll from;
bool operator <(const edge &a)const
{
return id < a.id;
}
bool operator ==(const edge &a)
{
return a.id == id;
}
};
ll n,m;
vector < edge > graph[N],inverse[N];
ll dist[N][N][4];
ll from_where[N][N][4];
bool is_interesting[M];
bool vis[N];
vector < edge > edges;
edge antestram;
void dijkstra(ll source,vector < edge > g[N],ll inv)
{
rep(i,0,n+1)
{
vis[i]=false;
dist[source][i][inv] = INF;
}
dist[source][source][inv] = 0;
rep(iterations,0,n)
{
ll cur = 0;
rep(i,1,n+1)
{
if(!vis[i] && dist[source][i][inv] < dist[source][cur][inv])
cur=i;
}
vis[cur] = true;
for(auto ed : g[cur])
{
ll v = ed.to;
ll cc = ed.cost;
ll ide = ed.id;
if(ide == antestram.id)
{
continue;
}
if(dist[source][v][inv] > dist[source][cur][inv] + cc)
{
from_where[source][v][inv] = ide;
dist[source][v][inv] = dist[source][cur][inv] + cc;
}
}
if(cur == antestram.from)
{
ll v = antestram.to;
ll cc = antestram.cost;
ll ide = antestram.id;
if(dist[source][v][inv] > dist[source][cur][inv] + cc)
{
from_where[source][v][inv] = ide;
dist[source][v][inv] = dist[source][cur][inv] + cc;
}
}
}
return;
}
void find_interesting(ll source,ll inv)
{
rep(i,0,n+1)
{
if(i == source)
continue;
is_interesting[from_where[source][i][inv]] = true;
}
return;
}
ll do_normal(ll id)
{
ll u = edges[id].from;
ll v = edges[id].to;
ll D = edges[id].reverse_cost;
ll c = edges[id].cost;
ll goton = min(dist[1][n][0],dist[1][v][0]+dist[n][u][1]+c);
ll goto1 = min(dist[n][1][0],dist[n][v][0]+dist[1][u][1]+c);
ll path = goton+goto1;
return path + D;
}
ll do_interesting(ll id)
{
antestram = edges[id];
antestram.from ^= antestram.to;
antestram.to ^= antestram.from;
antestram.from ^= antestram.to;
dijkstra(1,graph,2);
dijkstra(n,graph,2);
return dist[1][n][2]+dist[n][1][2]+antestram.reverse_cost;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
rep(i,0,m)
{
ll a,b,c,d;
cin >> a >> b >> c >> d;
edges.push_back({b,c,d,i,a});
graph[a].push_back({b,c,d,i});
inverse[b].push_back({a,c,d,i});
}
antestram.from = -1;
antestram.id = m+2;
dijkstra(1,graph,0);
find_interesting(1,0);
dijkstra(1,inverse,1);
find_interesting(1,1);
dijkstra(n,graph,0);
find_interesting(n,0);
dijkstra(n,inverse,1);
find_interesting(n,1);
ll ans = dist[1][n][0] + dist[n][1][0];
rep(i,0,m)
{
if(is_interesting[i])
ans=min(ans,do_interesting(i));
else
ans = min(ans,do_normal(i));
}
if(ans < INF)
cout << ans << "\n";
else
cout << -1 << "\n";
return 0;
}
/*
4 4
2 1 0 1
4 2 0 2
1 3 0 0
4 1 0 3
*/
