#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>;
const int N = 1e6+5;
const int INF = 1e9;
const int mod = 1e9+7;
vector<aa> adj[100005];
map<int,int> mp[100005];
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;
}
for(int i=2;i<=n;i++) {
d[i]=1e18;
}
priority_queue<ii,vector<ii>,greater<ii>> q;
q.push({0,1});
while(!q.empty()) {
ii u=q.top();
q.pop();
if(u.fi>d[u.se]) continue;
for(aa v:adj[u.se]) {
v[1]=min(v[1],mp[u.se][v[2]]-v[1]);
if(d[v[0]]>u.fi+v[1]) {
q.push({d[v[0]]=u.fi+v[1],v[0]});
}
}
}
if(d[n]==1e18) {
cout << -1;
return 0;
}
cout << d[n];
return 0;
}
/*
██╗░░██╗██╗░░██╗░█████╗░███╗░░██╗░██████╗░ ░██████╗██╗██╗░░░██╗ ░█████╗░██╗░░░██╗████████╗███████╗
██║░██╔╝██║░░██║██╔══██╗████╗░██║██╔════╝░ ██╔════╝██║██║░░░██║ ██╔══██╗██║░░░██║╚══██╔══╝██╔════╝
█████═╝░███████║███████║██╔██╗██║██║░░██╗░ ╚█████╗░██║██║░░░██║ ██║░░╚═╝██║░░░██║░░░██║░░░█████╗░░
██╔═██╗░██╔══██║██╔══██║██║╚████║██║░░╚██╗ ░╚═══██╗██║██║░░░██║ ██║░░██╗██║░░░██║░░░██║░░░██╔══╝░░
██║░╚██╗██║░░██║██║░░██║██║░╚███║╚██████╔╝ ██████╔╝██║╚██████╔╝ ╚█████╔╝╚██████╔╝░░░██║░░░███████╗
╚═╝░░╚═╝╚═╝░░╚═╝╚═╝░░╚═╝╚═╝░░╚══╝░╚═════╝░ ╚═════╝░╚═╝░╚═════╝░ ░╚════╝░░╚═════╝░░░░╚═╝░░░╚══════╝
*/
