#include<bits/stdc++.h>
using namespace std;
#define S second
#define F first
#define ll long long
//#define int long long
//#pragma GCC optimize("Ofast, unroll-loop")
//#pragma GCC target("avx,avx2")
#pragma GCC optimize("O3")
const int inf=0x3f3f3f3f;
const ll inff=0x3f3f3f3f3f3f3f3f;
const int X=1000000007;
vector<array<int,4>> adj[100005];
vector<pair<int,int>> cs[100005];
priority_queue<array<ll,4>,vector<array<ll,4>>,greater<array<ll,4>>> pq;
ll len[800010], ans=inff;
int col[400005];
map<pair<int,int>,ll> chg; //charge for node, color
signed main(){
ios::sync_with_stdio(0), cin.tie(0);
memset(len,0x3f,sizeof len);
int n, m; cin >> n >> m;
for(int i=1 ; i<=m ; i++){
int a, b, c, p; cin >> a >> b >> c >> p;
adj[a].push_back({b,c,p,i<<1});
adj[b].push_back({a,c,p,i<<1|1});
chg[{a,c}]+=p;
chg[{b,c}]+=p;
col[i<<1]=c;
col[i<<1|1]=c;
}
len[1]=0;
pq.push({0,1,1,0}); //length, node, edge, paid?
while(!pq.empty()){
auto[l,u,e,pd]=pq.top();
pq.pop();
if(len[e*2+(pd>0)]<l) continue;
if(u==n) ans=min(ans,l);
for(auto[v,c,p,i]:adj[u]){
ll f=chg[{u,c}]-(col[e]==c ? pd : 0LL);
if(l+p<len[i<<1|1]){
len[i<<1|1]=l+p;
pq.push({l+p,v,i,p});
}
if(l+(f-p)<len[i<<1]){
len[i<<1]=l+(f-p);
pq.push({l+(f-p),v,i,0});
}
}
}
cout << (ans==inff ? -1LL : ans) << '\n';
return 0;
}
