#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N=100'005;
const int M=200'005;
const ll INF=LLONG_MAX/2;
int n,m;
int eu[M],ev[M],ec[M],ew[M];
vector<tuple<int,int,int>> adj[N];
vector<int> id[N];
vector<ll> sum[N];
vector<array<ll,2>> dp[N];
vector<array<bool,2>> vis[N];
priority_queue<tuple<ll,int,int,int>,vector<tuple<ll,int,int,int>>,greater<tuple<ll,int,int,int>>> pq;
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n >> m;
for(int i=0;i<m;i++){
cin >> eu[i] >> ev[i] >> ec[i] >> ew[i];
adj[eu[i]].emplace_back(ev[i],id[eu[i]].size(),id[ev[i]].size());
adj[ev[i]].emplace_back(eu[i],id[ev[i]].size(),id[eu[i]].size());
id[eu[i]].emplace_back(i);
id[ev[i]].emplace_back(i);
}
for(int i=1;i<=n;i++){
int k=id[i].size();
dp[i].assign(k,{INF,INF});
vis[i].assign(k,{false,false});
sum[i].assign(k,0);
}
for(int u=1;u<=n;u++){
map<int,ll> mp;
for(auto [v,ui,vi]:adj[u]){
int cc=ec[id[u][ui]];
int ww=ew[id[u][ui]];
mp[cc]+=ww;
}
for(int i=0;i<id[u].size();i++){
sum[u][i]=mp[ec[id[u][i]]];
}
}
for(auto [v,ui,vi]:adj[1]){
int cc=ec[id[1][ui]];
int ww=ew[id[1][ui]];
dp[v][vi][0]=sum[1][ui]-ww;
dp[v][vi][1]=ww;
pq.emplace(dp[v][vi][0],v,vi,0);
pq.emplace(dp[v][vi][1],v,vi,1);
}
for(auto &x:vis[1]){
x[0]=x[1]=true;
}
while(!pq.empty()){
auto [d,u,i,t]=pq.top();
pq.pop();
if(vis[u][i][t])continue;
vis[u][i][t]=true;
if(u==n){
cout << d;
exit(0);
}
int c=ec[id[u][i]];
int w=ew[id[u][i]];
for(auto [v,ui,vi]:adj[u]){
int cc=ec[id[u][ui]];
int ww=ew[id[u][ui]];
ll d0=d+sum[u][ui]-ww-(t&&c==cc?w:0);
ll d1=d+ww;
if(!vis[v][vi][0]&&d0<dp[v][vi][0]){
dp[v][vi][0]=d0;
pq.emplace(d0,v,vi,0);
}
if(!vis[v][vi][1]&&d1<dp[v][vi][1]){
dp[v][vi][1]=d1;
pq.emplace(d1,v,vi,1);
}
}
}
cout << -1;
}
