#include<bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
using ll = long long;
using ii = pair<ll, ll>;
using aa = array<int,3>;
using aa4 = array<int,4>;
const int N = 1e6+5;
const int INF = 1e9;
const int mod = 1e9+7;
vector<aa> adj[100005];
map<int,int> mp[100005];
map<int,int> d[100005];
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,m;
cin >> n >> m;
for(int i=1;i<=m;i++) {
int u,v,c,w;
cin >> u >> v >> c >> w;
adj[u].push_back({v,w,c});
adj[v].push_back({u,w,c});
mp[u][c]+=w;
mp[v][c]+=w;
d[u][c]=1e18;
d[v][c]=1e18;
}
for(int i=2;i<=n;i++) {
d[i][0]=1e18;
}
priority_queue<aa,vector<aa>,greater<aa>> q;
q.push({0,1,0});
while(!q.empty()) {
aa u=q.top();
q.pop();
if(u[0]>d[u[1]][u[2]]) continue;
for(aa v:adj[u[1]]) {
if(u[2]!=0 &&v[2]!=u[2]) continue;
int cur=mp[u[1]][v[2]];
if(d[v[0]][0]>u[0]+cur-v[1]) {
q.push({d[v[0]][0]=u[0]+cur-v[1],v[0],0});
}
if(u[2]!=0 &&v[2]==u[2]) continue;
if(d[v[0]][v[2]]>u[0]) {
q.push({d[v[0]][v[2]]=u[0],v[0],v[2]});
}
v[1]=min(v[1],cur-v[1]);
if(d[v[0]][0]>u[0]+v[1]) {
q.push({d[v[0]][0]=u[0]+v[1],v[0],v[2]});
}
}
}
for(int i=1;i<=n;i++) {
//cout << d[i][0] << endl;
}
if(d[n][0]==1e18) {
cout << -1;
return 0;
}
cout << d[n][0];
return 0;
}
/*
██╗░░██╗██╗░░██╗░█████╗░███╗░░██╗░██████╗░ ░██████╗██╗██╗░░░██╗ ░█████╗░██╗░░░██╗████████╗███████╗
██║░██╔╝██║░░██║██╔══██╗████╗░██║██╔════╝░ ██╔════╝██║██║░░░██║ ██╔══██╗██║░░░██║╚══██╔══╝██╔════╝
█████═╝░███████║███████║██╔██╗██║██║░░██╗░ ╚█████╗░██║██║░░░██║ ██║░░╚═╝██║░░░██║░░░██║░░░█████╗░░
██╔═██╗░██╔══██║██╔══██║██║╚████║██║░░╚██╗ ░╚═══██╗██║██║░░░██║ ██║░░██╗██║░░░██║░░░██║░░░██╔══╝░░
██║░╚██╗██║░░██║██║░░██║██║░╚███║╚██████╔╝ ██████╔╝██║╚██████╔╝ ╚█████╔╝╚██████╔╝░░░██║░░░███████╗
╚═╝░░╚═╝╚═╝░░╚═╝╚═╝░░╚═╝╚═╝░░╚══╝░╚═════╝░ ╚═════╝░╚═╝░╚═════╝░ ░╚════╝░░╚═════╝░░░░╚═╝░░░╚══════╝
*/
