#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5;
const ll M = 2e5;
const ll inf = 1e18;
vector<pair<ll,ll>>e[N+M*2];
ll dist[N+M*2];
map <ll,ll> f[N];
vector <array<ll,3>> edges[M];
priority_queue <pair<ll,ll>> pq;
ll vis[N];
ll cnt = 0;
int main(){
ll n,m;
cin>>n>>m;
for(ll i = 0;i < m;i++){
ll u,w,c,d;
cin>>u>>w>>c>>d;
u--;w--;c--;
f[u][c]+=d;
f[w][c]+=d;
edges[c].push_back({u,w,d});
}
///two consective of the same color has a special case
///how to implement??? is the only way to make additions to graph?? ew
cnt = n;
for(ll i = 0;i < m;i++){
for(auto j:edges[i]){
e[j[0]].push_back({j[1],min(j[2],f[j[0]][i] - j[2])});
e[j[1]].push_back({j[0],min(j[2],f[j[1]][i] - j[2])});
if(!vis[j[0]]){
vis[j[0]] = cnt++;
}
if(!vis[j[1]]){
vis[j[1]] = cnt++;
}
//cout<<vis[j[0]]<<' '<<vis[j[1]]<<'\n';
e[j[1]].push_back({vis[j[0]],0});
e[j[0]].push_back({vis[j[1]],0});
e[vis[j[0]]].push_back({j[1],f[j[0]][i] - j[2]});
e[vis[j[1]]].push_back({j[0],f[j[1]][i] - j[2]});
}
for(auto j:edges[i]){
vis[j[0]] = 0;
vis[j[1]] = 0;
}
}
for(ll i = 0;i < cnt;i++){
dist[i] = inf;
}
dist[0] = 0;
pq.push({0,0});
while(!pq.empty()){
ll d = -pq.top().first;
ll id = pq.top().second;
pq.pop();
if(d > dist[id])continue;
for(auto i:e[id]){
if(dist[i.first] > i.second + d){
dist[i.first] = i.second + d;
pq.push({-dist[i.first],i.first});
}
}
}
if(dist[n - 1] == inf)dist[n - 1] = -1;
cout<<dist[n - 1]<<'\n';
return 0;
}
