#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf (long long)(1e15)
signed main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
//start here
int N,M;
cin >> N >> M;
vector<vector<array<int,3>>> edges(N+1);
vector<map<int,vector<pair<int,int>>>> color_edges(N+1);
vector<map<int,int>> total(N+1);
for(int i = 0;i < M;i++){
int a,b,color,cost;
cin >> a >> b >> color >> cost;
edges[a].push_back({b,color,cost});
edges[b].push_back({a,color,cost});
color_edges[a][color].push_back({b,cost});
color_edges[b][color].push_back({a,cost});
total[a][color] += cost;
total[b][color] += cost;
}
vector<map<int,int>> dist(N+1);
priority_queue<array<int,3>,vector<array<int,3>>,greater<array<int,3>>> pq;
// M+1 is king
dist[1][M+1] = 0;
pq.push({0,1,M+1});// dist,idx,in_color
while(!pq.empty()){
auto [cdist,cur,ccolor] = pq.top();
pq.pop();
if(dist[cur][ccolor] != cdist)continue;
if(ccolor == M+1){
// this is a king node
for(auto [nxt,color,w]:edges[cur]){
// to color node, chose direct
if(!dist[nxt].count(color) || cdist+w-w < dist[nxt][color]){
dist[nxt][color] = cdist+w-w;
pq.push({dist[nxt][color],nxt,color});
}
// to king node, chose direct or indirect
int ndist = cdist+min(w,total[cur][color]-w);
if(!dist[nxt].count(M+1) || ndist < dist[nxt][M+1]){
dist[nxt][M+1] = ndist;
pq.push({ndist,nxt,M+1});
}
}
}else{
for(auto [nxt,w]:color_edges[cur][ccolor]){
// choose other, so become king node
if((!dist[nxt].count(M+1) || total[cur][ccolor]-w+cdist < dist[nxt][M+1])){
dist[nxt][M+1] = total[cur][ccolor]-w+cdist;
pq.push({dist[nxt][M+1],nxt,M+1});
}
}
}
}
if(!dist[N].count(M+1)){
cout << "-1";
}else{
cout << dist[N][M+1];
}
}
