#include <bits/stdc++.h>
using namespace std;
long long const INF=1e18;
int const MAX=1e5+5;
struct edge{
int nod,col,pr;
};
vector<edge>G[MAX];
map<int,long long>dp[MAX];
map<int,vector<edge>>Gcol[MAX];
map<int,long long>sum[MAX];
int n,m;
void read(){
cin>>n>>m;
int i;
for(i=1;i<=n;++i)
dp[i][0]=INF;
for(i=1;i<=m;++i){
int u,v,col,pr;
cin>>u>>v>>col>>pr;
G[u].push_back({v,col,pr});
G[v].push_back({u,col,pr});
dp[u][col]=INF;
dp[v][col]=INF;
Gcol[u][col].push_back({v,col,pr});
Gcol[v][col].push_back({u,col,pr});
sum[u][col]+=pr;
sum[v][col]+=pr;
}
}
struct path{
int nod,restr;
long long dist;
};
class cmp{
public:
bool operator()(path a,path b){
return a.dist>b.dist;
}
};
long long dijkstra(){
priority_queue<path,vector<path>,cmp>pq;
dp[1][0]=0;
pq.push({1,0,0});
while(!pq.empty()){
auto [nod,restr,dist]=pq.top();
pq.pop();
if(dp[nod][restr]!=dist)
continue;
if(restr==0){
for(auto [vec,col,pr] : G[nod]){
if(dist+pr<dp[vec][0]){
dp[vec][0]=dist+pr;
pq.push({vec,0,dist+pr});
}
if(dist+sum[nod][col]-pr<dp[vec][0]){
dp[vec][0]=dist+sum[nod][col]-pr;
pq.push({vec,0,dist+sum[nod][col]-pr});
}
if(dist<dp[vec][col]){
dp[vec][col]=dist;
pq.push({vec,col,dist});
}
}
}
else{
for(auto [vec,col,pr] : Gcol[nod][restr])
if(dist+sum[nod][restr]-pr<dp[vec][0]){
dp[vec][0]=dist+sum[nod][restr]-pr;
pq.push({vec,0,dist+sum[nod][restr]-pr});
}
}
}
if(dp[n][0]==INF)
dp[n][0]=-1;
return dp[n][0];
}
int main()
{
read();
cout<<dijkstra();
return 0;
}
