#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<pair<int,int>> adj[N];
map<int,vector<pair<int,int>>> adjc[N];
map<int,ll> sum[N];
map<int,array<ll,2>> dp[N];
map<int,array<bool,2>> vis[N];
bool vis2[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],i);
adj[ev[i]].emplace_back(eu[i],i);
adjc[eu[i]][ec[i]].emplace_back(ev[i],i);
adjc[ev[i]][ec[i]].emplace_back(eu[i],i);
dp[eu[i]][i]={INF,INF};
dp[ev[i]][i]={INF,INF};
}
for(int u=1;u<=n;u++){
for(auto [v,i]:adj[u]){
sum[u][ec[i]]+=ew[i];
}
}
for(auto [v,i]:adj[1]){
dp[v][i][0]=sum[1][ec[i]]-ew[i];
dp[v][i][1]=ew[i];
pq.emplace(dp[v][i][0],v,i,0);
pq.emplace(dp[v][i][1],v,i,1);
}
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);
}
if(!vis2[u]){
vis2[u]=true;
for(auto [v,j]:adj[u]){
if(i==j)continue;
ll d0=d+sum[u][ec[j]]-ew[j];
ll d1=d+ew[j];
if(d0<dp[v][j][0]){
dp[v][j][0]=d0;
pq.emplace(d0,v,j,0);
}
if(d1<dp[v][j][1]){
dp[v][j][1]=d1;
pq.emplace(d1,v,j,1);
}
}
}
if(t){
for(auto [v,j]:adjc[u][ec[i]]){
ll d0=d+sum[u][ec[j]]-ew[j]-ew[i];
if(d0<dp[v][j][0]){
dp[v][j][0]=d0;
pq.emplace(d0,v,j,0);
}
}
}
}
cout << -1;
}
