#include <bits/stdc++.h>
using namespace std;
#define MAX 101000
typedef pair<long long,long long> pii;
typedef pair<long long,pii> pip;
vector<pip> con[MAX];
unordered_map<long long,long long> custao[MAX];
map<long long,long long> mamg[MAX];
int main(){
// freopen("main.in", "r", stdin);
// freopen(".out", "w", stdout);
int n,m;
cin>>n>>m;
for(int i=0;i!=m;++i){
long long a,b,c,d;
cin>>a>>b>>c>>d;--a;--b;
custao[a][c]+=d;
custao[b][c]+=d;
con[a].push_back({b,{c,d}});
con[b].push_back({a,{c,d}});
}
priority_queue<pii,vector<pii>,greater<pii>> queue;
queue.push({0,0});
bool visitou[n]={};
long long valores[n]={};
long long custo=0;
while(queue.size()){
auto _ = queue.top();
queue.pop();
if(visitou[_.second])continue;
visitou[_.second]=true;
valores[_.second]=_.first;
for(auto&x:con[_.second]){
if(mamg[x.first].find(x.second.first)==mamg[x.first].end())
mamg[x.first][x.second.first]=_.first;
long long ajuda=_.first;
auto it = mamg[_.second].find(x.second.first);
if(it!=mamg[_.second].end())ajuda=it->second;
queue.push({min(ajuda+custao[_.second][x.second.first]-x.second.second,_.first+x.second.second),x.first});
}
}
if(!visitou[n-1]){
printf("-1\n");return 0;
}
cout<<valores[n-1]<<"\n";
}
