#include <bits/stdc++.h>
#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 1e3+5, M = 2e3+5;
struct edge{
int v, c, p;
};
int dp[N][M], from[N][M];
vector<edge> adj[N];
map<int,int> sum[N];
signed main(){
fastio
int n,m;
cin >> n >> m;
for(int i = 0;i < m;i++){
int u,v,c,p;
cin >> u >> v >> c >> p;
adj[u].push_back({v,c,p});
adj[v].push_back({u,c,p});
sum[u][c] += p;
sum[v][c] += p;
}
fill(&dp[0][0],&dp[N-1][M-1],1e18);
priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<>> pq;
dp[1][0] = 0;
pq.push({0,{1,0}});
//dis, vertex, lst
while(!pq.empty()){
auto [ww,pp] = pq.top(); pq.pop();
auto [u,cc] = pp;
if(ww > dp[u][cc]) continue;
for(auto [v,c,p] : adj[u]){
//Dont change this edge, change all others
if(cc!=c){
if(dp[v][c] > dp[u][cc]+sum[u][c]-p){
dp[v][c] = dp[u][cc]+sum[u][c]-p;
from[v][c] = p;
pq.push({dp[v][c],{v,c}});
}
}
//Change this edge, using p
{
if(dp[v][0] > dp[u][cc]+p){
dp[v][0] = dp[u][cc]+p;
pq.push({dp[v][0],{v,0}});
}
}
}
}
int ans = 1e18;
for(int i = 1;i <= m;i++){
ans = min(ans,dp[n][i]);
}
cout << (ans==1e18 ? -1 : ans) << "\n";
}
