#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
using ll = long long;
const int N = 205, M = 5e4 + 5;
const ll inf = 0x3f3f3f3f3f3f3f3f;
ll dis1[N], dis2[N], dis3[N], dis4[N], dis5[N], dis6[N];
// 1-n, n-1, 反转边 i-1, i-n, 重新跑的 1-n, n-1 
int fa1[N], fa2[N], mrk1[N], mrk2[N];
// 最短链
int delnum, addu, addv, addw;
int p[M], w[M];
pii e[M];
vector<pii> g1[N], g2[N];
vector<int> num[N];
int n, m;

void dij(int s, vector<pii> *g, int zt){
	vector<ll> dis(n + 5, inf);
	vector<int> vis(n + 5);
	dis[s] = 0;
	priority_queue<pair<long long, int>> q;
	q.push({0, s});
	while(!q.empty()){
		int u = q.top().second;
		q.pop();
		if(vis[u])	continue;
		vis[u] = 1;
		// 重跑 dij 的新边 
		if(u == addu){
			if(dis[u] + addw < dis[addv]){
				dis[addv] = dis[u] + addw;
				q.push({-dis[addv], addv});
			}
		}
		int pos = 0;
		for(auto x : g[u]){
			int v = x.first, w = x.second;
			if(zt == 5 || zt == 6)
			if(num[u][pos] == delnum)	continue;// 删边操作 
			if(dis[u] + w < dis[v]){
				if(zt == 1)	fa1[v] = u;
				if(zt == 2)	fa2[v] = u;
				dis[v] = dis[u] + w;
				q.push({-dis[v], v});
			}
			pos++;
		}
	}
	for(int i = 1;i <= n;i++){
		if(zt == 1)	dis1[i] = dis[i];
		if(zt == 2)	dis2[i] = dis[i];
		if(zt == 3)	dis3[i] = dis[i];
		if(zt == 4)	dis4[i] = dis[i];
		if(zt == 5)	dis5[i] = dis[i];
		if(zt == 6)	dis6[i] = dis[i];
	}
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n>>m;
	for(int i = 1;i <= m;i++){
		int u, v;
		cin>>u>>v>>w[i]>>p[i];
		g1[u].pb({v, w[i]});
		num[u].pb(i); 
		g2[v].pb({u, w[i]});
		e[i] = {u, v};
	}
	dij(1, g1, 1);
	dij(n, g1, 2);
	dij(1, g2, 3);
	dij(n, g2, 4);
	int uu = n;
	if(dis1[n] < inf)	while(uu != 1)	mrk1[uu] = 1, uu = fa1[uu];
	uu = 1;
	if(dis2[1] < inf)	while(uu != n)	mrk2[uu] = 1, uu = fa2[uu]; 
	// 查询最短链 
	
	ll mincost = dis1[n] + dis2[1];
	for(int i = 1;i <= m;i++){
		int u = e[i].first, v = e[i].second;
		if((fa1[v] == u && mrk1[v]) || (fa2[v] == u && mrk2[v])){ // 只要在最短链上就重新搞 
			int wt1 = 0, wt2 = 0;
			if(fa1[v] == u && mrk1[v]){// 如果 (u, v) 在 1-n 最短路上 
				// 如果在最短链上重新做 dij
				delnum = i;
				addu = v, addv = u, addw = w[i];
				dij(1, g1, 5);
				wt1 = 1;
			}
			if(fa2[v] == u && mrk2[v]){// 如果边在 n-1 最短路上 
				delnum = i;
				addu = v, addv = u, addw = w[i];
				dij(n, g1, 6);
				wt2 = 1;
			}
			mincost = min(mincost, (wt1 ? dis5[n] : dis1[n]) + (wt2 ? dis6[1] : dis2[1]) + p[i]);
			continue;
		}
		
		// 1-v, u-n, n-1
		mincost = min(mincost, min(dis1[n], dis1[v] + dis4[u] + w[i]) + min(dis2[1], dis2[v] + dis3[u] + w[i]) + p[i]);
//		mincost = min(mincost, dis1[v] + dis4[u] + dis2[1] + p[i] + w[i]);
		// 1-n, n-v, u-1
//		mincost = min(mincost, dis1[n] + dis2[v] + dis3[u] + p[i] + w[i]);
	}
	if(mincost >= inf)	cout<<-1<<'\n';
	else
		cout<<mincost<<'\n';
	return 0;
}